I've had this issue with some websites that use transactional e-mail services to send their e-mails. A temporary failure on your domain or email provider will flag the address as bad seemingly permanently on their e-mail provider's side so that it will instantly fail any future sending attempts to that address even after the original issue is resolved.