Search in Finder/Spotlight etc doesn't work

Safe Boot from the HD, (holding Shift key down at bootup), does the problem occur in Safe Mode?

Safe mode attempts to repair Disks & clears lots of caches, so if Safe Mode works try again in regular boot.

I've used this for years to really find stuff...

Find Any File...

http://apps.tempel.org/FindAnyFile/index.php

Hold Option or alt key when selecting Find to Find All.

OOPs, you mistakenly marked it solved. :(

Manually Rebuilding Spotlight via Terminal

If the aforementioned Spotlight control panel approach doesn’t spur a reindexation of the drive, you may need to initiate it manually through the command line. Open Terminal and use the following command string to do so:

sudo mdutil -E /

This basically asks for temporary super user status, which is why Terminal may ask you for your password (it may not if you’ve used a sudo command recently or are already logged in as a super user or root. The command asks the unix tool mdutil to reindex the spotlight database for everything on the computer, including external drives, mounted disk images, etc. To re-index only for a specific drive, use the /Volumes path. For example, for an external drive named “MiniMe,” the command would look like this:

sudo mdutil -i on /

Rebuilding a drive index can take a long time, so be prepared to wait whether you do it through the System Preference panel or the command line.