I've got an issue with my domain. Whenever a user creates a calendar appointment request the email notification automatically gets sent to the deleted items box.
I've done a message trace and I can see
The message was delivered to the Deleted Items folder.
There's no rules set for the users, and I can't see any settings in the Exchange Admin console that would affect this.
Automatic processing might trigger this, check the options under Calendar > Automatic accept or decline > Auto accept/decline. Another possibility is a hidden rule, check via MFCMAPI or similar low level tools.