I know it's not easy, but it's not impossible either. Besides, every country with mobile coverage has one or two dominant players which means that the number of deals might be manageable. They can gain more efficiency if they reach multi-country deals with multi-national carriers such as Vodafone or (please god no) Orange.

And I was thinking the music-supporting Kindle might be an entertainment device to rival the iPods not the iPhone. Imagine a device with books and music: it would be an awesome mobile entertainment device. They already have most of (all?) the necessary hardware in the Kindle 2.