Today a customer ran into an interesting issue. A user was not able to send out email to external recipients (this was already the case for a couple of weeks) but internal email, both in Office 365 as well as hybrid Exchange 2010 did work fine.

The NDR that was returned to the user said:

Delivery has failed to these recipients or groups:
jaapwess@gmail.com
Your message couldn’t be delivered because you weren’t recognized as a valid sender. The most common reason for this is that your email address is suspected of sending spam and it’s no longer allowed to send messages outside of your organization. Contact your email admin for assistance.

At first, the only I read was “Your message couldn’t be delivered because you weren’t recognized as a valid sender” so it took me some time to figure out what was wrong.
It’s not a permission issue (was my first thought) but Exchange Online Protection is blocking the account because of spam.

Even in a hybrid scenario with centralized mail transport this can happen, because Exchange Online outbound mail (to Exchange 2010 on-premises) is still handled by Exchange Online Protection.

To check the outbound spam and the user that is blocked, open the Exchange Online Admin Center, select protection in the navigation bar and click the action center tab. Here you can see the user account that is blocked, including the reason and date for blocking as shown in the following screenshot:

For this specific user:

Reason:
OutboundSpamLast24Hours=122;OutboundMailLast24Hours=128;OutboundSpamPercent=953;Last Message MessagetraceId:4495783e-13af-483c-b8d2-08d643c0f46c

Date:
11/6/2018 8:22 AM

So, it was already blocked for 9 days and 122 outbound spam messages were detected the last 24 hours.

I asked the local IT guys to go to this specific workstation, perform an ant-virus run to clean-up the workstation so I can unlock the account.

Update. Some items from the protection and/or compliance center are moving to the Security & Compliance Admin Center (https://protection.microsoft.com). You can find the restricted users (i.e. users that are blocked from sending outbound email) under Threat Mangement | Review and Restricted Users.