If so is it the uninstall of zip folder support that actually fixes the problem?

Yep. I disable it since I install WinRAR almost instantly after I get a system up. Follow these directions to unregister the DLL responsible for ZIP folders. To ensure the thing stays disabled, delete the file from both the system32 directory, and the dllcache folder in system32.

And yes, as everyone else confirmed, the XP version of TweakUI allows you to change search to match 2000's look and feel. I advise everyone running XP to download it and go page by page through all the options. I also like it for the task bar managment. I like the grouping feature so that multple task bar entries from one program are all next to each other, but I despise when it makes them all merge into one icon on the taskpar (since there is no easy way to undo that), so Tweakl UI allows me to set that threshold to 99.

There is a ton or other tips over on the TweakXP site.