Search doesn't work consistently in IE from sidebar or header

Tried this in a a few different templates and in both IE for the mac & IE on Windows 2000. Keep running into the same problem.

Got this report from my client:
"When we type anything (ex. Afghanistan) in IE search box, there are no results. It seems like the string is not passed at all. The stranger part is that if we just clicked on the submit with the default text (search text) in there, IE does produce results."

I only use Windows through Browsercam, but was able to find similar results in IE for the Mac and Windows. This all works just fine in Firefox and Safari btw.

However, in IE for Windows if you search for a term (say 'ThisDoesNotExist') which isn't found the function search_view() doesn't seem to recognize the $_POST['op']. It doesn't seem to send people to:
http://www.example.org/search/node/ThisDoesNotExist

but rather to:
http://www.example.org/search/node/

It does seem to work fine if you search from the default search box that appears in the content here:
http://www.example.org/search/node/

But fails if you use the one in the header or the blocks. I tried this with box_grey, bluemarine, and a custom theme. Done lots of validation.

I'm really not sure how to go about resolving this problem.

Mike