You're running IE8 aren't you?

The reason I ask is that I noticed when I saw Google had
finally 301 redirected their non-www address to the www version they're doing it the same way most do, with a stock, very short message that just says the page has moved. These short messages with content in the mere couple hundred bytes range can cause some browsers to do weird things because of what I consider to be a flaw IE that has pretty much always required web pages to be larger than 512 bytes in order to actually display the page. There is actually a Registry setting for this 512 byte threshold.
IE, prior to version 8 would simply not display a custom error page if it was less than 512 bytes. Or crap out if a redirect was less than 512 bytes.
In IE8 this behavior has changed. Now when it sees a page of less than 512 bytes it
redirects the user to Bing.com.
So there's your spyware most likely. It's IE8.

What's the moral of the story?
For webmasters the moral is that your custom error pages and other redirects should be configured to be more than 512 bytes, meaning (I believe, though I've not looked at it lately) you can't use any of the standard Apache messages because they're all less than 512 bytes out of the box. Note also that if you have compression enabled it needs to be larger than 512 bytes after compression. If you neglect to do this IE8 is going to automatically send traffic from your site to Bing.com whenever users hit a 404 error or any other redirected page.
And people wonder why I've been disallowing IE8 to be installed on my computer...

FTR, some have reported non-domain queries being sent to whatever default search provider you have set up in IE8. Some who have say Google.com set up as their default search provider are still getting Bing.com for non-domain hits, strongly suggesting an NXDOMAIN hijack in IE8. While this may be related to your error/redirect experience, it's not quite the same thing since we know the domain hostname does in fact exist.
No matter how you slice it it's a flaw in IE. Always has been, always will be, and no I don't expect them to ever change it.