If you have trouble in sending mails between two Domino servers over a VPN connection and all Domino settings are right, decrease the MTU size of the server.
If your Domino server is a Windows machine:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Tcpip\Parameters\Interfaces {Interface ID} MTU -> 1006
In this case 1006 was a good value. (CISCO VPN Concentrators on both sides)