thegallery, I wonder whether your problem may go away if you enable the Indexing service. This is supposed to use spare processor cycles to index the files on your computer, making the search function much quicker.
The Index Service isn't normally enabled because some people find it slows their PC down
You can enable Indexing by going to Start | Search | Change Preferences and choosing With Indexing Service. Choose the option Yes, enable Indexing service and press OK.
Your PC will then begin making an index of all the files on your PC, hopefully causing the searches to be faster.
If it doesn't work I'd recommend switching the Index service off again.