@chripuck actually most of Europe have excellent cell service.
Costs of calling between countries are also fair, due to the fact that the EU monitors the market, most recently this resulted in EU setting the maximum cost of sending an SMS within the EU to 0.11€(~0.15 USD). And no, we don't pay to receive the message.
Source
http/www.mobileburn.com/news.jsp?Id=5359
Your concrete example a German user calling in France will, cost 0.48 €(~0.67 USD) a minute, hardly an arm and a leg. That by the way is also a max price fixed by the EU.
Source
http/www.mobileburn.com/news.jsp?Id=3396
About exclusive phones it's funny you brought up Germany and France. In Germany T-Mobile was forced, by the courts, to offer an unlocked iPhone and in France they already have the laws forbidding the exclusive bundling of cellphones to carriers.
The iPhone is one of the few cases this wasn't a good idea, probably because of Apples special deals with carriers, as the 2007 introduction prices for unlocked phones was 999€ in Germany and 749€ in France. There were however also offers with a contract that was available at a lower cost.
Apart from the iPhone most phones are carried by several carriers, and sold without carriers from electronic stores and supermarkets, meaning we got competition. We seldom pay more for the phone and a contract(with included talk) than the phone on it's own(without a contract).
I still can't believe people in the US can't see they're in a market favoring the carriers instead of favoring the consumers, like the one in Europe. If our way is Socialism I'm sure most Americans wopuldn't mind a little socialism in their lives.