I still prefer things stay clean and in order.
I would strongly urge you to give up that ghost when it comes to computer databases. The information IS clean and in order, but it's in computer order, not human. I speak from a decade plus of software support. If the only thing it bothers is your OCD (yes, it gets to me too), then you should walk away from the database and let it be.
Here's the gist of what you have to do (and if you don't take a backup before you start in on this, you will cry).
Turn off letting people sign up. For now.
Make a note of everyone's OLD and NEW user ids, because you will need to EDIT every post and comment to the new IDs. Also, you have to update the entire wp_usermeta table to point to the new ones.
I poked around a little and I can't find where the user count is located. It MAY be just as simple as 'what's the last one? Okay, insert a new one' but I don't know for sure. You may have to do some serious digging into the database and functions.