a lot of times, outlook accesses the exchange server using the NetBIOS name. Do you have an ip address defined for your exchange server on the oulook client?
if you do, can you telnet to the exchange server on port 25.e.g,
telnet x.x.x.x 25
if that works, that means you have tcp connectivity and you are running into some MTU/fragmentation issues