I've always done sortm -verbose after big delete fests. verbose because I love watching the towers of hanoi shuffle along.
lots of GUI mail systems have 'compact mailbox' command options. I assumed that everyone did periodic tidyup anyway.
I'm not saying this isn't a problem. But, I seriously wonder how BIG a problem this is. If you can renumber out of it, then isn't that a viable work-around?
-G