Wait a minute!
I just realized that the problem of dealing with Deleted messages has a much simpler solution than I was thinking. Each deleted message has an X-Status: D line in the header. If I need to go back and re-mark them or remove them (expunge them) after the fact, those can be done at any time! The header lines are still in each message!
There could be a simple re-mark script or expunge script to do this.