Since you didn't mention the VPN solution, I'll give you my old standby
answer...
1) Change the authentication type in Outlook 2003 from Kerberos/NTLM to just
NTLM. (Some VPN solutions drop the Kerberos UDP packets)
2) Verify name resolution is working over the VPN connection. (Means test
DNS & WINS name resolution using nslookup and nbtstat)