email/smtp issues

one of our clients has been having issues with external outgoing emails being returned undeliverable for different reasons, which is perplexing to me. One reason said “SMTP communication problem with recipient’s email server”, another said “you do not have permission to send to this recipient”, and another one said “Configuration error on server”.
When only 2 users (that I know of) are having problems, and there isn’t any consistency in the stated reasons, what could the issue possibly be?
I’m perplexed. Any tips and hints would be greatly appreciated.