May be you can try this weared regedit thing .... run regedit and find this entry :
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer\NoFind
It'll probably have value set to "01 00 00 00" ... you should change it to "00 00 00 00" .... I didnt find the entry cuz I'm working on windows 2000 right now. So please post your comments when you've done it.