I would go so far as to say: governments themselves are "free-market monopolies" in this sense. That is, there is no binding unilateral authority which solves intergovernmental disputes, and each government instead has to negotiate with other governments in an open and unregulated forum where even backstabbing and flagrant contract violations are permitted. If governments are monopolies on power, then the market of power is surely not a well-regulated one.
Pepsi and Coke are not a monopoly - as you explicitly acknowledge, there are at least two suppliers in this market.
Microsoft was never a monopoly, there were always other suppliers (Sun, Be, IBM, Apple, Linux, at different points in time).
On your point, it could be argued that Google's overall platform dominance might not be attributed to barriers to entry, but rather barriers to exit. While Google offers some of your data back to you in a portable format it's still quite difficult to leave their services, and even when you do they will still be tracking you for advertising. To form their potential natural monopoly in your mind, you can imagine how difficult and inefficient it would be to have multiple different firms tracking you to the same extent that Google does (search, Google+, Gmail, calendar, Google Docs).
I am not an amateur economist.