I was going to ask how much time had passed since you updated the OAB as it takes up to 24 hours for it to be downloaded. But that would not give you the Exchange error.
You don't have a firewall on the XP machines that could be blocking ports, do you?
Oh, do you have Office 2007 SP2 installed? It fixes some of the problems. http://support.microsoft.com/kb/968858