After deleting mailbox by using Exchange Task wizard from Active Directory, your exchange will not automatically delete those mailboxes. And you won’t be able to delete exchange mailbox as the option will be grayed out. It is because there is “Deleted Mailbox Retention” policy which is there to protect you from yourself. After a certain number of days the mailboxes will automatically be purged.
However if you want to delete the mailbox immediately follow the below steps
- Open Exchange System Manager
- Expand Administrative Group and Go to your Mailboxes node
- Right click on Mailboxes node and click on Run Cleanup agent
- Now you can permanently delete those mailboxes
Sayem's Blog 