A lot of people a lot smarter than either you or i have spent a lot of time writing extremely efficient queueing mechanisms that are guaranteed to scale a lot better than anything we're going to be able to write in Perl. I wrote a proof of concept application a month or two ago, and for my queueing mechanism I used Qmail. I could just as easilly have used sendmail or any of the MTA's out there. Why? Simple... guaranteed delivery, well understood API, guaranteed locking, guaranteed atomicity, you can bundle any data you want with each queue request (just bundle it as a MIME attachment) etc...

I'm going to argue that this is one of those situations where you just don't want to bother... I mean, hell, Java had to invent the entire JMS (Java Messaging System) to create persistent queues and a relatively performant API, and even with all of SUN's resources behind the project, a lot of people are chosing simpler solutions... Seriously, don't reinvent the wheel... write 2 programs, one that sends email, one that checks the Inbox... you'll be happy that you did.