I recently started playing with MQTT http://mqtt.org for Android as a way of doing what you're asking for (i.e. not SMS but data driven, almost immediate message delivery, scalable, not polling, etc.)
I have a blog post with background information on this in case it's helpful http://dalelane.co.uk/blog/?p=938
(Note: MQTT is an IBM technology, and I should point out that I work for IBM.)