I've found that "unpredictable" deliveries are most often associated with: 1) misconfigured or obsolete multiple MX hosts e.g., the primary MX host "works" but the secondary doesn't relay -- the secondary isn't used during "normal" but may be involved when the primary (or its network) is unavailable 2) out of synch DNSes for the mail domain 3) night-time maintenance of the customer's authentication system such that the SMTP dialog will fail to verify the existence of the mailbox 4) misconfigured or misdesigned anti-spam program/filters 5) the phase of the moon /Pete