This functionality is required by a lot of people. No one as yet has taken up on creating a plugin like this. Milbo, I am sure that you will make a log of people happy by creating such a plugin that can manipulate invoice and order number.
Why dont you take it up? How much will this cost? I am sure lost of people will be ready to pay for this. I am.