I've seen a couple of other posts by people having the same issue, one of the Cox people mentioned a potential issue regarding 3rd party clients.
Try providing the following info for them:
- Name of the program used to check mail (Outlook, Mac Mail, etc)
- Time of day that the problems usually occur (or if all day say all day)
- Carrier for the cell phone
- Brand of cell phone
- Are you using the stock mail app?
- Does the problem occur when you are at home and on wifi?
- What are the specific error messages or codes that you are getting when there is an error?
They might need different information, but that was usually good enough for me to go on to at least start diagnosing an exchange issue.