GG, I believe your rig may be infected by Windows. Unfortunately, the only way to fix the infection is a complete wipe and degaussing of the HDD.
On a serious note...I'm running Vista on my laptop and can search just fine. Not sure what the problem is in your case but I believe everyone else already covered possible causes.
Quote: "For the record, I'm not a fan of this newfangled style of searching in comparison to XP"
Yeah, just one of the "I'm not a fan of" items with each release of Windows.
I've included a screenie of my search settings if you want to take a look.
In Development: K96 - Combat Simulation
Keep your Hope and Change, I choose individual Liberty!