Agreed. I lived in Germany for about 9 months last year. I had cell service for about 15€/month. It really sucked to come back to the US and pay $100/month for worse service.
A lot of it is coverage. I could pay substantially less if I was willing to go with a worse network. How much would it cost you for a plan that covered all of Europe?