This was a old issue that was addressed in the 7.5x series. Which you have so I would suggest open a support ticket so Rick can take a look at it.
I don't know why you would delete a message in the tables. But you may try the "Content rebuilder" in the ubb control panel now, to see if it corrects the problem.
