I'm looking for a message queue as a service that ..
I only found CloudAMQP (still in beta), AppEngine Task Queue (not AWS), SQS (polling only), Redis To Go (no high availability? -twitter stream seems full of issues) and IronMQ (polling only).
What am I missing?
Looks like Iron.io have added pub/sub. Maybe it fits your needs now? Also, it appears to talk beanstalkd, so you're potentially free to migrate easily to a self hosted solution at some point in the future (should you feel that urge!).