Interesting; looks like DirectoryQueue uses directories, rather than file locks (man 2 flock), to lock the queue messages. This might actually work, since mkdir returns an error if you attempt to create a directory that already exists. The implementation seems to be handling most of the obvious failure cases, or at least tries to.
So how does one lock a message in s3? Does s3 have a "createIfDoesNotExistOrError"? I'm still having difficulty understanding how the proposed system avoids race conditions.
Back in 2000, I worked with a guy that built an entire message queue product using the SMTP protocol with an implementation that was in turn built on top of lex and yacc.
The Perl implementation was the original AFAIK.
http://search.cpan.org/dist/Directory-Queue/