Running Exchange 2003 SP2 - Experiencing a strange issue where a disabled or deleted user object in AD, with ticked the "mark exchange mailbox for deletion" but it is not flagging the mailboxes for deletion. Purge and reconnect are greyed out but can still access "exchange tasks". Run Cleanup agent is selected with no outcome. AD replication has been forced in ADSS MMC between all DC's in NTDS Settings.I have also checked mailbox status using ESM through "MMC" and manually choosing the DC.

So, the issue is, the mailbox didnt show as deleted (Red cross on the mailbox) via ESM after you have deleted the user object via ADUC, right? When did the user object been deleted? The action wont take effect immediately, please restart Microsoft Exchange Information Store service, and then use Run Cleanup Agent again, see if the mailbox appears as deleted If not, please create a test user and the mailbox, and then try to reproduce the issue, see if the issue still persists. If yes, please see the related events in the application log on the exchange server