844 kilobytes of overhead in 2 weeks? No big deal. That means 844 kilobytes of data was deleted out of that table in 2 weeks. That ain't a whole hell of a lot. And your MySQL sure as heck isn't running slower for it. I think you're really going overboard with worry on this.
People are going to be deleting private messages or deleting or editing posts all day every day. It's going to make for an amount of overhead/dead space. Don't let yourself get into a position where you're freaking out over a little overhead every time someone deletes a PM. Your board doesn't even notice the difference.
Spend the time enjoying your board instead.
![[Linked Image from navaho.infopop.cc]](http://navaho.infopop.cc/progress.gif)
