You managed to get 1 of the many Microsoft mysterys.

Normally, I'd say it somehow just emptied the deleted items, but you claim otherwise.

Could you please check your emtied messages in Extra> Recover deleted message's?
This is just to make sure that this isn't the case. It has to done fast though, because they don't save there for a long time.