Use your favourite jabber/XMPP server and you immediately have a messaging system with authenticated entities, status updates, queueing of messages when a server is unavailable, etc. And even better, you can add your servers as contacts in your favourite chat client and send them instructions yourself!
Here at Twitter we use an in house, open source solution, called
Kestrel which has great performance.
http://github.com/robey/kestrel/tree/master
Robey Pointer wrote it, and it's quite good. It uses a simple memcache
interface.
Set = enqueue. get = dequeue.
-john