The other part that caught my attention was:
Cannot send mails to mail server. (Mailbox unavailable. The server response was: 5.7.1 Requested action not taken: message refused).
Do all emails come from the same email address and/or use the same login credentials? Does it use trusted connectivity or no security? And you have indicated this only sometimes happens? Is this query the only one that fails?
I just thought of something.. Exchange verifies that a mailbox exists for mailboxes it hosts so if you try to send to an email address that doesn't exist I can see this happen. Verify that all the recipients exist and that their names are spelled EXACTLY correct.
CEWII