I know what you're referring to... I've seen it before. It's just that after I do this "fix" it just stays the "magnifying glass". And it's still not updating.
This is a brand new computer... and I've had this problem from the get-go. So weird!
OnyX? NO! Bad idea! Completely ruined my Leopard system. Had to reinstall. Maybe I was just unlucky, but others have had (slightly less serious) problems.
Of course, I see. When I had a similar problem, I turned to FileBuddy for its search abilities. I'm sure there's a freeware utility available that can accomplish the same, perhaps at Versiontracker.com.
run this command and paste the output back here in this thread:
sudo mdutil -s /Volumes/"root volume"
where "root volume" is the name you have given your (duh) root volume. I think it defaults to "Macintosh HD". Does it say "Indexing Enabled"? Try a spotlight search from the command line: