Can't delete a relationship
This issue can be caused because the relationship is in alert because you deleted the user's mailbox. There is no way to fix this so you would right click, select delete and go through the motions to try to remove the destination copies. In a public to private relationship, or a private to private relationship in this case, cleanup is not possible. Since A2E will not automatically delete an alerted relationship, it will stay in the Trash until you select to Empty the Trash from Global options.
In a prior release we had issues emptying the trash so please update to the latest version. http://support.diditbetter.com/kb/A2E_194.aspx