Just bought my first album from the aforementioned Amazon MP3 Store.
It was great. $9.99, using my Amazon-registered credit cards and billing address. Little downloader app works great and seamlessly. It didn’t nag me at all. The songs downloaded very quickly and were automatically added to iTunes with complete metadata and album art.
Apple might have a little more to worry about than I thought. Once you’ve tried the Amazon MP3 store, there’s absolutely no strong incentive to buy any other music from iTunes if it’s available on Amazon, and there are two strong incentives (price and format versatility) in the other direction.