We've got a mailbox for each department (e.g [email protected] and [email protected]) and everyone in that department has access to it, access is granted using Exchange Management Console.

If I send a calendar invite to [email protected], I get a Undeliverable report:

Delivery has failed to these recipients or groups:

User_A The e-mail address you entered couldn't be found. Check the address and try resending the message. If the problem continues, please contact your helpdesk.

User_B
The e-mail address you entered couldn't be found. Check the address and try resending the message. If the problem continues, please contact your helpdesk.

User_C
The e-mail address you entered couldn't be found. Check the address and try resending the message. If the problem continues, please contact your helpdesk.

The users are no longer in AD or Exchange but we cannot find any mention of them within any deligates or permissions anywhere.

We only started to get this problem AFTER we upgraded our DCs from Windows Server 2003 to Windows Server 2008 and Exchange server from Windows Server 2003, with Exchange 2005 to Windows Server 2008, with exchange 2010.