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.
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.