[Response to Steve]
Steve-
Have the users in question been given Full Mailbox Access? If so, then the permissions are meaningless because once you log into a mailbox with an account that has Full Mailbox Access, the permissions are not checked. One thing you might want to check is to make sure that these users cannot access any other folder in the mailbox other then the Calendar folder. If they can, then something is up.
Another thing that could cause a problem is if the Security Descriptor on the Calendar folder is no longer MAPI Canonical. You can use the PFDAVADMIN tool mentioned in a previous comment to check to make sure that the Security Descritor is properly ordered.
--Chris