That particular response from Outlook when trying to get data from Exchange is called an RPC Cancel Request dialogue. It is really a non-specific error that can be a challenge to troubleshoot. With the VPN, I suspect it is just taking a little too long for all the components to be reached and for a message to send. Name resolution slowness or Active Directory performance may contribute to this problem as well. You might try a hosts file entry for the Exchange server for the VPN clients. If the VPN is strictly for Outlook connectivity, you might consider RPC/HTTPS as an alternative.
As a general methodology for troubleshooting those RPC cancel requests, there is a kb article 839862: http://support.microsoft.com/?id=839862. I imagine the VPN is really the contributor here though, as you have proven connectivity without it.