Are you using Time Machine? Any other back up method?
Have you tried searching with Finder? Not via Spotlight, click on your Desktop and make sure Finder is active. Now press command and f to get a Finder search window. Do NOT use the Spotlight entry box.
I have just downloaded Easy Find which is now helping me, but why won't spotlight work?