I have installed and configured Exchange 2013 from scratch on a new DC for a customer who had Exchange 2003 in a separate domain with 30 users.
The customer exported all the PST of their users's outlook application into a shared folder which then I used to import through Exchange Administrator Center by giving the appropriate rights to the Exchange Admin that I am using and everything went smooth.
Users can use outlook, inside and outside and can receive all the imported mails without any issue. and I have setup a new test e-mail for my self with at least 15 test mail inside it.
When I setup my new account on their phones, I have no issues what so ever but if I setup any of their accounts they can't receive any email and when they try to send an email it says "Cannot Send Mail" the message was rejected by the server.
I am attaching mobile screenshots of the message and the settings! note that the emails were set automatically by Autodiscover service.
If anyone has clue why would this happen I would appreciate it.
Just a small notice, the old FQDN for the DC was domain (Without .local or .com or anything) and the new one is domain.local.
Customer is using iPhone 5 with iOS 8.1.2 firmware version!