You have deleted a user's mailbox, but following PureMessage AD synchronization, the mailbox re-appears.
First seen in
PureMessage for Microsoft Exchange
When the mailbox is deleted by disabling the mailbox from the Exchange console, all the Exchange attributes are removed except the mail attribute. This is believed to be an Exchange 2010 issue.
What To Do
You must delete the 'mail' attribute manually from affected users.
This can be done using the Microsoft tool ADSIEdit. For further information, refer to the Microsoft article: ADSI Edit (adsiedit.msc)