Marking Quarantine Notice senders as safe for entire tenant

Thanks to Community redacting your details we can't see if there is any obvious mistake in your left-hand side choices on the notice addresses. 

Have you checked that your recipients have not reported their own quarantine notices? If you are using the Exchange Online powershell you can check that with:

get-MailboxJunkEmailConfiguration -identity user@domain | `

 Select -ExpandProperty BlockedSendersAndDomains

However, you mention that many users have the problem so this explanation seems unlikely.

Assuming the right hand sides align with your Accepted Domains, the other thing to check is that the public DNS records (MX, SPF and DMARC if it is in use) are correct.