As an aside: If you're not willing to make that substantial kind of change to your system at this point, I would at least recommend basing your messaging system on something that's designed to do it (i.e. a message queue) as opposed to a relational database. RabbitMQ has had quite good reviews from what I've seen, with clustering and persistence available.