It seems that greasemonkey scripts are interfering with the search function completely, it won't search at all with them switched-on.

If I turn it off and search, save the search and switch back on, the saved searches work fine, it's just the search box that is broken.

I'm using

Improved Remember the milk overview
A bit better RTM
Remember the milk fat free