Can you check and confirm if this issue is with just a specific set of users or multiple users. If its is with a specific set of users. Try sending a test email and check if internal emails work just fine. If Internal emails don't work check the email address and proxy address attributes.
If the issue is only with External emails in that case DBEB could possibly be blocking the emails. Try setting up the type of accepted domain from Authoritative to Internal Relay and test sending the emails and see if you get similar error.