Several users are unable to send email to public folders. They get NDR's back. The public folders have Default and Anonymous set to contributor.

To add to the mystery, these same users can send to the public folders successfully through Outlook Web Access.

We were able to solve the mystery. Turns out there is a corrupted group that all the users belong to. We found this out by trying to copy the AD account of one of the users having the problem. The copy failed and complained that it could not copy the group membership because 'object could not be found'. It gave the DN of the group. The way we interpret this, is the Public Folders where using the default group / everyone to grant access. Since the Store could not enumerate group membership, it was denying the delivery of mail from these users.