If it was a DB corruption, then that could help but OP stated that he deleted the messages himself. I am not 100% sure whether it makes a difference, of course it might be that the entries in DB are not scrapped immediately, only marked as deleted?