Make sure you have high TCP ports open. Go to TechNet and do a search on Static Port Mapping on Exchange to see how it uses ports when talking to a client.
We run into the same problem here with some clients. We have a 3005 in a DMZ and exchange servers outside the DMZ. It seems that if you do static port mapping for your exchange server, it speeds things up. On Exchange, the client talks to the por...