The following call : EcLocallyDeliverMsg2 to the store failed. Error code : 1238 (Message-ID <firstname.lastname@example.org> will be NDR'd). MDB : 87b7cb4d-7e6b-47fa-be39-85b0d7995226. FID : . MID : . File : C:\Program Files\Exchsrvr\Mailroot\vsi 1\Queue\NTFS_e1be85a401c83c0400000024.EML.
Well, that didn't clarify much. A quick internet search turned up this Microsoft KB article: http://support.microsoft.com/kb/873393, but that definitely was not my case.
Giving the issue more thought, I realized that in attempt to secure the access to the folder as much as possible I went a little too far by disallowing any access to Anonymous users. Now, when an external SMTP server submits an email to Exchange server, this is anonymous access as far as Exchange server is concerned. Thus the attempt to submit a message to the public folder is denied! The solution was to allow "Contributor" access to the Anonymous user.
The bottom line is that if an Exchange public folder is to receive email from an external SMTP server, Anonymous users should be allowed "Contributor" access.