Its a copout answer, but I'd be real unsurprised if the problem were indigenous to WinME. Sounds like a corruption issue, either in Registry or with Search, or with both.
Still, there's a possible solution. I've had that problem with WinME. You might wanna create a Restore Point, then create a folder on your Desktop, with a short, distinctive name, like "TweakUI", go to
TweakUI for WinME, read the page, including the instructions, and download TweakUI directly from Microsoft into that folder you just created.
When the download is complete, open the folder and double-click the icon to run the self-extract, then, after you've read the "Readme", of course

, right click on
tweakui.inf and select "Install". A "Help" Window may pop open, if it does, just close the window that comes up and allow Install to finish. When the installation is complete, TweakUI will appear in Control Panel, and you may delete the download folder if you wish.
If you're unfamiliar with TweakUI, here a few caveats:
1) Don't uncheck "Search Results" on the Desktop tab. No-brainer, here ... this one is the point of the exercize.
2) Don't uncheck "Show Control Panel on Start Menu" on the IE tab; doing so would prevent you from accessing either Control Panel or TweakUI ... not good. Not good at all.
3) Another no-brainer: Don't "Hide" the TweakUI icon on the Control Panel tab. In fact, its a pretty good idea to create a Desktop Shortcut to TweakUI.
4) Don't change the "My Computer" icon on the Desktop tab. Doing so will cause Active Desktop problems, and could result in a wholebuncha script errors in Special Folders in either WebView or Active desktop ... very aggravating. It could do some other wierd stuff too, none of which is at all amusing.
5) Don't uncheck "Shell Enhancements" on the IE tab. Doing so hauls out a whole raft of unexpected and tricky-to-figure-out-and-fix problems all over the place. You really, really,
really don't wanna go there.
I found that solved the "Disappearing Search" problem for me, and, eventually, I figured out all that other stuff I warned you about. That took a while. But "Search" worked. If it hadn't, finding-and-fixing woulda taken a whole lot longer, at the very least.