Been doing some research : the problems appears related to corruption in the INDEXING. See below: Broken search in Windows 7 Libraries
The suggested fix seems to be creating a new user profile - quite an extreme and unorthodox "fix" to say the least. Microsoft really needs to look into this more.
This poses a conundrum for me, since I have turned OFF indexing since my C: is a SSD (and that is where the Library is stored/acccessed) but my photo's are physically saved in E: (spinner drive). I don't think turning OFF indexing is the cause of the problem since its not mentioned in the link above.
Anyone using a SSD have the same problems? BTW : you will see this issue simply by trying to arrange the default Sample Pictures under Public Pictures (see below).