Ok, I couldn't wait, so I released the fix already (first post updated)
Bira, please try it on your huge database, it should work fine, but let me know if it doesn't, for any reason... It takes less than 5 seconds to run on my database, and I have over 60k posts.
So anyway, this fixes your pitfall #1. Now let's talk about your pitfall #2. First of all, many people will not consider it a problem, but a "feature", since even though some of this user's posts were deleted, this still remains his Xth post, and there is no reason to modify this. This is a "logical" issue, if you will. In any case, I have decided to make it part of the hack after all.
Anything else I can do for you, sir?