Currently Being ModeratedFeb 15, 2013 8:09 AM (in response to James Rothschild)
From the errant clients: use Connection Doctor (Mail.app > Window > Connection Doctor) to test the access.
From the server: Review the mail server log activity around the time of the failures (SMTP server log, POP/IMAP server log, and — if nothing is showing up there — your gateway and any local or gateway firewall logs), perform the usual SMTP/ESMTP server and POP/IMAP server settings comparisons, get off of port TCP 25 for submitting mail from clients, and stay out of 192.168.0.0/24 and 192.168.1.0/24 if any VPNs are in use.
More advanced: Test a connection to port 25 or whatever you're using as a submission port from the remote network, too. You can use telnet or the openssl s_client to connect into the target port (cleartext or SSL/TLS) and verify connectivity. (Though Connection Doctor will usually tell you about this.)
Once you figure out one of the misbehaving Mail.app clients, you'll probably have the rest sorted out, too.