A recent change in Exchange online seems to have caused a problem with mail enabled public folders receiving messages from people outside of the organisation. It has never been necessary with Office 365/Exchange Online to give create permissions to the anonymous or default users , you could instead set the mail flow settings of the public folder to allow anonymous access.

You may see the following bounce message when sending to a mail enabled public folder:

Delivery has failed to these recipients or groups:

Your message wasn’t delivered due to a permission or security issue. It may have been rejected by a moderator, the address may only accept email from certain senders, or another restriction may be preventing delivery. For more tips to resolve this issue see DSN code 5.7.1 in Exchange Online. If the problem continues contact your help desk.

5.7.1 RESOLVER.RST.AuthRequired; authentication required [Stage: CreateMessage]>’

Of course it is possible and easy to set permissions for the public folder from Outlook to solve this problem, but doing this does not seem to be working for everyone. Some people are reporting success with it, but others not.

Setting the public folder permissions with PowerShell fixes the problem, but I cannot understand why there is a difference.

Setting Offiec 365 Public Folder Permissions with Powershell

In order to fix this problem you have to grant create permissions to anonymous and the default user. The Powershell cmdlet to do this is Add-PublicFolderClientPermission.

After connecting to Office 365 Remote Powershell as described here, you can run the following commands:

Add-PublicFolderClientPermission -identity "\test public folder" -User Anonymous -AccessRights CreateItems
Add-PublicFolderClientPermission -identity "\test public folder" -User Default -AccessRights CreateItems

Once you have added the permission it’s probably best to give it a quick check with:

Get-PublicFolderClientPermission -identity "\test public folder"

Hope this helps.