After reading through all the comments I tried to authenticate to Exchange using the IP instead of the FQDN. And it worked! Seems like a problem with address resolution or storing of a hostname instead of an IP adress.
After reading through all the comments I tried to authenticate to Exchange using the IP instead of the FQDN. And it worked! Seems like a problem with address resolution or storing of a hostname instead of an IP adress.