A method of "stateful failover" is provided that allows email gateway systems in a cluster to deliver email messages that have been accepted for delivery by a member of the cluster, but has failed with out delivering the messages. The method involves creating a backup copy of the messages that have been accepted for delivery by one email gateway system in the stateful failover cluster on one or more other email gateway systems in the stateful failover cluster. Upon detecting the failure of the email gateway system that accepted the message, another member of the stateful failover cluster that has access to the backup copy of the message queue takes responsibility for the delivery of the messages on the mirrored queue.