Enter Net::Amazon::SimpleQueue, a wrapper to the Amazon Simple Queue Service. The messaging system is now a web service. Interestingly they expose it as both a SOAP and a REST (ok, not really REST as everything is a GET) service. Now this won't solve all your messaging needs (there are some limitations), but it's fast and reliable. What if you could use Amazon for infrastructure? As an aside, the Amazon Web Services Blog has been fairly interesting recently.
Now I haven't seen many uses of the service yet, but that's because there wasn't a simple Perl interface. Now there is, so go get hacking!