I-Phone and exchange woes

Ok I have a client who while in his office space is able to send and receive messages just fine from his phone. The moment he leaves the office however he is no longer able to send from his phone and gets an error stating:

"Cannot Send Mail. A copy has been placed in your Outbox. The recipient "username@domain.com" was rejected by the server." (obviously I've changed the email address given).

Now the strange thing about this is it is happening on 3 different I-Phones with at least 2 different carriers (Sprint and Verizon). There are other I-Phones in the office on both of these carriers which work fine. We have compared the settings to these and they are identical. We changed the the server configuration from the FQDN to the exact IP address with no luck. The other working phones in the office can send to the exact same username with no errors so it is not a username issue. The affected phones are able to send the emails while on the office networks wi-fi but not when they go onto their respective carriers. SSL is not used in this instance. When configured the phones reports that everything works the way they are supposed to but it still rejects the sent email when it is attempted. We have deleted the accounts and re-added them to no avail. We have deleted all other email accounts on the phones and re-added the affected account only to no avail. Quickly running out of ideas here folks. Any help would be appreciated. Thanks!:confused

Seems as if it fails no matter if it is on WiFi or on the carrier. Really confused here.....