A DigitalPoint Forums thread reports that MSN Search (aka Live.com) is indexing permanent 301 redirects. What this means is that if you search on a term or command that triggers the domain that is 301ed to show up, it will show something like the following in the search results.
Moved PermanentlyThe document has moved here. Apache/2.2.0 (Fedora) Server at www.xxxxxxxxxxxxxxx.com Port 80
Some members have confirmed this to be true, but I personally tested serveral domains that I know are 301 redirected and was not able to reproduce it.
I am thinking it may be about the server type, the configuration and so on. But also, related to how Live.com handles those server responses.
Forum discussion at DigitalPoint Forums.