Its the SAMe Problem in Vista... Its the new Windows Indexing that enables fast searching when hitting the windows icon and when you type something in...
Here's the solution

1) Press the Windows Icon
2) In the search bar (how ironic, right

) type in "indexing options", hit enter
3) Modify the Locations where you actually use the search (For me its just "Start Menu" and "Contacts") It comes with the searching the whole Netbook by default!
Should be it,
if not!, try selecting no Location at all, and stop ur AV-Application and see if that helps...