I am sure bing/msft also does everything they can to 'understand' me, but at least they don't see my browsing history or emails.
Now back to beating Google - I do believe it's possible, but Google will soon catchup with any potential competition. They will catchup because it's their bread and butter and they have perhaps the worlds biggest concentration of technical personnel. The best way to beat any product/company is to be considerably better than it in at least few areas, given the scale of web indexing, that is a very very tough job only few companies can pull through.
Microsoft has/had a good chance to beat Google, but Microsoft is considered a bigger evil/corporate than Google, so they have a slim chance to emotionally overcome Google, not to mention technical capability. But they can perhaps open source bing in an effort to beat Google, provided they have the will and moolah to do so. When I mention open source, it's not the code, but the underlying search index, exposed as an API, free of use for anyone/any product. That will dramatically shift the emotion as well as the usage towards bing. I even mentioned this during an internal bing meetup event (I am part of a bing beta testers group), but of course no one listens.
A startup can also try to beat Google in their wildest dreams if they can associate themselves with the younger crowd like snapchat did and the younger crowd somehow finds it hip/cool to not use Google and use that service instead, and provided they get a decent web search data/index from established competition like bing or they manage to index themselves. These are few of the possibilities.