any chance that you were accessing the same mailbox from a different machine - e.g. an iPhone or Android phone?
Last week had something very similar where a mailbox was being accessed by a Mac and an iPhone and deleting stuff on one, simply moved it on the other to an obscure folder.