Windows

Directory replication does not replicate the mailboxes - it just replicates defined directories. You can also replicate public folders between the two servers but not mailboxes. An Exchange mailbox is homed on a particular server and can exist only in one place.

There is no easy way and the only method I'm personally familiar with would be a server cluster but that would not work in your present network configuration and would require that both servers participate in a cluster.

On this forum, I have occasionally heard mention of a server-mirroring product called Vinca but I don't know whether it would play nicely with Exchange.

As a far reach, you could, I suppose, create mirrored mailboxes on each server by creating a mailbox for each user on both servers and then define the mailbox on the alternate server as an alternate recipient of any mail sent to the mailbox on the primary server. However, if you can afford to duplicate the storage and double the traffic, you can probably afford a cluster