When you run the rules wizard and try to apply a rule to certain mailboxes, the rules wizard will return the following error: Failed to login into <MAILBOX> with hr = 0x80004005
Microsoft Exchange 2003
To solve this problem, you would need to remove deleted users' mailboxes manually. This can be done as follows:
Open Microsoft Exchange System Manager
Change to Administrative Groups > First Administrative Group > First Storage Group > Mailbox Store > Mailboxes
Right click Mailboxes and select Run Cleanup Agent
You would notice that the mailboxes that the rules manager has problems accessing will have an icon with a red cross. Right click the mailboxes with the red cross and select Purge.
After purging all the mailboxes that do not have a user, close Exchange System Manager
Try to run the rules manager
When you delete an user from Microsoft Active Directory the mailbox will be marked for deletion; however, it will not be removed from the Microsoft Exchange Information Store. The rules manager will still detect such mailboxes, but it will not be able to apply the rules onto these mailboxes.