This look like the same problem that I have. My company Mail for Exchange will only serve requests that came through GPRS-type access networks and not the general Internet. To access these services, you should make a packet data call (even if there is a WiFi connection available, you should route MfE to this network; if you are using a 3G or GPRS connection to the internet, you should also use a different Access Point -- or even drop this 3G/GPRS connection, if you can't support two connections at the same time).

This type of arrangements have probably been made because of security concerns (even if beliefs rather than pure facts), i.e. the transmission path from the point to gateway is strictly contained within standard telecom packet networks.