Android & (millions of) push notifications

I'm working on the Android version of an application I first created on iPhone and this application requires to send (if it's as successful as its iPhone version) up to millions of push notifications to users daily.

I naively thought the Android platform had a push notifications service as its sibling so I decided to look at this feature at the end of development and now here i am!

I searched stackoverflow for answers about this feature (issue ?) and found several options (thanks guys!) BUT did any of you guys was able to achieve such a feature with such a volume?

Here's the options I found :

• Google's C2DM Framework : my first issue is that it's for Android 2.2 + only but I may consider it if there wasn't this 200.000 notifications a day quota; did any of you guys requested more quota from Google ?
• MQTT : this solution looks good and the sample code provided by Anton Lopyrev is helpful (and Dale Lane blog posts are a good read); this is the option I'm using right now but I have no idea about how it may react with thousand of users (I also have trouble with the server (mosquitto) OR the service (I don't know yet) and I am not able to receive notifications sometimes with 2 users :p)
• XMPP : it looks like the best option (yet ?) but I haven't tried it yet; did any of you guys use this solution ?

I've read about Xtify or Urban Airship but none of these commercial solutions may help (volume or cost).

Thanks for any tips!

Edit : my goal is to be able to send up to 5,000,000 notifications a day

200K is the development quota, we'll be happy to grant you more if you need it. Android 2.2+ represents >80% of Android devices in the field today. We typically turn these requests around pretty quickly.

http://developer.android.com/resources/dashboard/platform-versions.html