Lync 2010 Fail

Ahh.... big difference then. Given that the SRV records point to your domain but the IP is xxx.dedicated.lync.com, the client is always connecting externally. If the VPN tunnel prevents this connection, most likely the client cannot resolve 443 to ae1.032d.dedicated.lync.com due to either outbound firewall route paths that overwrite the client default settings.

I would look to see what the client receives for routing from the VPN connection and compare to an internal computer. They should have the same access out at least in regards to the Lync client. Again, this is also where the client logs an tcp dump should show what the client is attempting to do and what's not responding. I'd expect oneway traffic. If firewall, you should see some denies.