Unable to send emails to a mail enabled Public Folder

When trying to send emails to a mail enabled Public Folder your users receive the following NDR

Delivery has failed to these recipients or distribution lists:

emailaddress@domain.com
There's a problem with the recipient's mailbox. Microsoft Exchange will not try to redeliver this message for you. Please try resending this message, or provide the following diagnostic text to your system administrator.
_____

Sent by Microsoft Exchange Server 2007
Diagnostic information for administrators:

Generating server: htserver.domain.com

emailaddress@domain.com
#550 5.2.0 STOREDRV.Deliver: The Microsoft Exchange Information Store service reported an error. The following information should help identify the cause of this error: "MapiExceptionNotAuthorized:16.18969:E70F0000……

Error: MapiExceptionNotAuthorized makes it apparent that the issue is with permissions.

Check the public folder permissions, use PFDAVAdmin or Microsoft Outlook for it. Make sure that Anonymous has Contributor permission level.