Email with 19.8MB Attachment bounced as undeliverable - Domain Policy set to 25MB

Email with 19.8MB Attachment bounced as undeliverable - Domain Policy set to 25MB

Email with 19.8MB PDF attachment was returned as undeliverable with the following message

Delivery to the following recipient failed permanently:

User@domain

Technical details of permanent failure:
Google tried to deliver your message, but it was rejected by the server for the recipient domain { domain}  by  mx.zoho.com . [165.254.167.50].

The error that the other server returned was:
554 5.2.3 MailPolicy violation Error delivering to mailboxes

The domain policy has the max email size as 25Mb.

What seems to be the problem here?