I have a user who's Calendar invitations are showing up in the Deleted Items
folder instead of the Inbox, anyone know how and why this would happen?

Something is auto-processing them, either a mis-configured rule or a setting
misunderstood.

The first place to look would be:
- TOOLS
- OPTIONS
- E-MAIL OPTIONS... button
- TRACKING OPTIONS... button

There are a few things to look at in the "Tracking Options" window. You
need to look at them a kinda think about what they are really doing if they
are selected.

Then:
- TOOLS
- OPTIONS
- CALENDAR OPTIONS... button
- RESOURCE SCHEDULING... button

If the client has chosen to "Automatically accept meeting requests and
process cancellations", the key word here is "process..."