I agree that as a site owner you have the right to who has the ability to search your site, but when you start to have someone like Microsoft going around paying people to alter their robots.txt file to keep Google's crawlers out of it, I think you've stepped into distinctly different territory from a right of privacy.
Furthermore, I would make the argument that this is much different from signing a contract with a publisher. On the contrary, I would say this is akin to a movie theater paying a movie studio to keep a movie out of its competitor's theaters. This exact scenario was ruled to be a violation of the Sherman Antitrust Act: (http://en.wikipedia.org/wiki/United_States_v._Paramount_Pict...)
This sounds to me as though it's the exact type of anticompetitive action things like the Sherman Antitrust Act were meant to prevent.
The Paramount case was more about vertical integration than exclusive deals. Since Microsoft and News Corp are two completely separate companies I don't really see how that case applies.
Had Microsoft been making msnbc content exclusively available through bing then there might have been a case, but making a deal with News Corp shouldn't step on any of the ground covered by the Paramount case.
Furthermore, I would make the argument that this is much different from signing a contract with a publisher. On the contrary, I would say this is akin to a movie theater paying a movie studio to keep a movie out of its competitor's theaters. This exact scenario was ruled to be a violation of the Sherman Antitrust Act: (http://en.wikipedia.org/wiki/United_States_v._Paramount_Pict...)
This sounds to me as though it's the exact type of anticompetitive action things like the Sherman Antitrust Act were meant to prevent.
*Edit, added link to Paramount case