Thank you for showing me that configuration tester. I have used an online service from Microsoft a few times (as suggested by our Exchange admins) and that turned out just fine (that was 3 weeks ago). Just now I tested the Autodiscover feature again using the method you suggested, and that also returns a correct configuration.
I'm comparing the server settings in Mail on my MBA (10.8) with the settings on my MBP (10.7). On my MBP the Exchange account works just fine, on my MBA it doesn't (just to be clear).
On the MBP I have changed the internal server address to the same as the external one, because that's what always reachable on any network: wired, wireless or thru the Internet. The internal server address is only reachable when you're connected to the wired network.
On the MBA, I can change the server addresses all I want, but after closing and opening Mail again, it's all back to what autodiscover tells it should be. Which sounds OK, but down the line, this doesn't work, no matter what network I'm on: wired, wireless or thru the Internet: just the problems as described.
Now comes the interesting part: how does Mail (or any other Exchange enabled client) know which server to use: the internal or external one? To circumvent that, I used the external server address on Lion, because that's always reachable. On Mountain Lion however: how am I supposed to know Mail enforces the use of Autodiscovery, even if I change it? Mail could warn me: "Are you sure you want override these settings?" But it doesn't. It could also make the server address fields grayed out, meaning I can see what the settings are, but cannot change them. That is called feedback in usability terms. And if Apple decided to always honour the Autodiscovery information, why make the server address fields viewable or editable in the first place? It's not clear what the intentions are and apparently it's still pretty legit from an Exchange point of view to have a configuration like the one we have. It's our choice to shut down a few ports on wireless for security reasons. That is why there is an internal and external address field. But why does Mail not honour it's user, (with a warning) if he explicitly makes a change?