Processes in Microsoft 365 for setting up Office apps, redeeming product keys, and activating licenses.
It looks like Microsoft has issued a Hotfix that seems to resolve this (so far, so good, for me at least).
http://support.microsoft.com/kb/2899544
It does list this as one of the issues being fixed:
When you delete some selected email messages from a folder in Outlook 2013 by clicking the Delete button in the ribbon, these message items may still appear in the list, even though they are actually deleted.