Issue
An Office 365 mailbox has been deleted from tenant and from the backup sources but the backup still returns the warning "mailbox does not exist"
Resolution
To resolve login to the obm client with the customers credentials and go to backup sets. Select the desired set and go to I would like to choose what to backup.
In the top right hand corner there will be an option to change to view. Change this from explorer to table view.
Once the source is removed from here and the changes are saved the next backup should come without warnings.
This steps can also be carried out on the web portal: http://portal.vsl-net.com/backup