Outlook profile changes.

I've been changing some more user profiles in outlook this week as we've moved users across to a new server. On almost every machine I've had to blow away the user profile in outlook and recreate a new one.
The latest error message I got was on a client machine connecting to the lan via a VPN connection and getting a message "The Microsoft Exchange Server computer is not available. Either there are network problems or the Microsoft Exchange Server computer is down for maintenance." The weird thing is that I could telnet to the server, ping it, resolve names - just not open the mailbox on the server. After checking various things such as firewall configs,rpc ports I created a new profile - and it worked. Deleted the old one, tried to recreate it as best as I could and now the user is happy.