You have always been able to run non-Google services on your blog. In the same way you can use Yahoo's Flickr to post photos to your blog, you can include an MSN Search box in your template. We consider it a violation of the terms to modify the Blogger navbar, but that's not what was reported to have happened here. We did not send a request to have the MSN Search box removed. We reviewed the information that's been made available, and we found no such request from our support teams. We did not delete nor remove the blog in question from Blog*Spot.
I think it's very important that companies don't start restricting the use of competitor's services on their own services, as it would create an artificial market, possibly leading to a monopoly caused not by the overwhelming merit of a company or service above that of its competitors but because it was reasonably popular and had the strictest policies in stopping the use of competitors services.