If Roddy's information doesn't get it done, then most of the Autocomplete information is kept in the registry. Here is a link that should help you get rid of the "Search" information:
Clearing Windows Explorer/Autocomplete MRU Lists in the Registry
http://support.microsoft.com/support/kb/articles/Q142/2/98.asp
The above information is for Windows 9.x/ME..In Windows XP and I believe Windows 2000, the normal Search/Files and Folders MRU listing lies in the registry at this path:
HKCU\Software\Microsoft\Search Assistant\ACMru\5603
One important note, DO NOT DELETE the "Default" entry. You should notice that each search item has a name, like 001, 002, etc. If the addresses you deleted destroyed the numerical order of those names, the Search will only show those numbers that are numerically sequential, starting with url1. In other words, if you deleted 005, then the Search window would only show you 001 through 4, even though you might have 006 through 20 still listed in the Registry. It is easily fixed though, by renaming all the remaining listings to be sequentially in order. (Right click the name, choose 'Rename" and name it to the next number in the sequence. In the example above, 006 would be renamed 005, 7 would be 6, etc.)They then will be listed correctly in the Search window.
Hope this helps.
Grif