I've had this problem with my latest installation of Vista where the search wasn't finding anything. If I opened up "Indexing Options" from the control panel, it kept saying something ridiculous like "62 items indexed" - clearly I have more than 62 items to index!
Anyway, I figured out a work-around. From that "Indexing Options" window, click on Modify then Show all locations (you'll have to allow the UAC prompt). Next, uncheck everything, making a note of what you uncheck as you go.
From there, click OK to dismiss that dialog, then back in "Indexing Options" click Advanced and then rebuild. We you click OK again, you'll see it says "0 items indexed" and "Indexing complete" underneath that.
Good, you've "reset" the indexer, basically. Now, go back into Modify and re-check everything that was checked before. Click OK and you should see it start indexing again!
It'll take a little while for the index to build up but hopefully it doesn't get "stuck" anymore. Give it a couple of hours and you should see something like "62,343 items indexed" and "Indexing complete". If it gets stuck, it'll just always say "Indexing speed is reduced due to user activity"
Another funny thing I noticed is that it sometimes said "Indexing paused to conserve battery power" - even though this is a desktop computer and doesn't even have a battery! To fix this one, go into Control Panel and then "Power Options". Now, I had "High performance" checked there (and if you're a desktop computer, that's what you should have as well) so click on Change plan settings.
In this window, click on Change advanced power settings, then scroll down to Search and Indexing. I noticed on mine, it had Power Savings Mode set to Power Saver for some reason, so I just flicked it to High Performance and clicked OK. That solved that problem as well.
So there you have it, two problems solved in one day. Not bad :)