During its Graph Search announcement, Mark Zuckerberg noted that it will also include wider results thanks to Facebook's partnership with Microsoft and Bing. Apparently, same deal did not work out with Google.
It was pretty clear that Graph Search would need some sort of outside help as finidng people, dentists and restaurants would not make it a good search engine and thanks to Bing, it can pull in a whole lot more "results".
Zuckenberg noted that Facebook would love to work with Google as well and they simply just "wanted to incorporate search", but only as long as the company is willing to honor the privacy of folks sharing content on Facebook. Apparently, that could not work out with Google as Microsoft was more "willing" to do things specific to Facebook.
Of course, everyone is now waiting for a reply from Google as it looks like this is not over yet and we are quite sure that Google's reply will be quite interesting.