Check the account they get the message for in AD and make sure there are no restrictions on delivery to that account. We have some accounts noone is allowed to send to without permission. Are the same people denied permission to send to the same account every time? I find it hard to believe this is truly ‘random”. If it is, I would definitely call Microsoft for support on this one as it is NOT normal behavior for Exchange.
Also check that they are not sending from a shared mailbox. By default, any user other than the mailbox owner is not allowed to send from it (“send as” permissions).