Don't know if you're still looking for an answer - I'd guess it's a VPN port transparancy/ time out issue -.
What are you using to create the VPN on the mac, and how is the VPN terminated at the site? Do remote PC users have the same problems? If you dress a PC user up in the mac's VPN settings does it have a problem?
Do you know how to test if port 25 traffic is getting from the mac to the server? Found this:
Check port 25 in Mac OS
Each Mac OS is delivered with a preinstalled terminal emulator. The terminal is a tool which allows you to execute commands from the command line. Usually, the terminal is located under your Mac HD -> "Applications" directory -> Utilities sub-directory. When the window opens, you will see a command line with a flashing cursor on it so you can start typing right away. Just type the following command and press "Enter":
telnet my-domain-name.com 25
Give it a go and see if you get an answer from the exchange server when the mac is on the VPN.