I'm not sure your achitecture is exactly correct for the volume of traffic you're trying to deal with. You've gone for a batch approach (ie. put everything in a table, and check periodically), when perhaps a real-time approach (process messages as you receive them) will work better. The downside of a real-time approach, in this case, is that it's likely to be much more complex.

I've actually implemented something very similar to this. I'm assuming you need to queue messages, but they only need to be queued based on some critieria, ie, messages from two senders can run simultaneously, but messages from the same sender must be queued. (If all messages need to be in the exact same order, then you can't avoid full serialisation, so you're current approach will have to stick).

What we did was have Apache/mod_perl handle the requests, do some basic error checking, and then pass the request onto a custom written daemon via a socket.

The daemon has two main process. The first one lists for requests from Apache, and then forks to handle the request. The forked process then does it's thing. However, before it can do it's thing, it asks permission from the second main process - the serializer. The serializer has a hash table of processes currently running for each sender. If there is nothing running for that sender, it gives permission for the sender to go. Otherwise, it tells the sender to wait. You can also handle timeouts in this process as well.

The code for this is actually GPL'ed. I'm not sure if it'll be of any use, but you can have a look here (you want the fe-replication executable).