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