Trying to minimize your administrative overhead would be using an alternate solution to manually exporting/importing printer mappings on thousands of computers. Assuming a few things:
You have Active Directory Sites and Services configured with all of your sites and subnets.
You know which printers exist in which location.
This migration is being performed in stages, either by physical location or business unit.
You could fairly easily create and link site level GPO's to map the appropriate printers for the appropriate users/computers based on their site "affiliation".
You could work on this in parallel at the same time you're searching for a manual solution.
Addendum
I'm not trying to give you a hard time, but at what point do you start fixing the things that need fixing and start managing the environment in a more effective and efficient manner? I understand that it's a lot of work, but how long are you going to continue down this road? You've admittedly stated that things are a mess. When do you start cleaning up the mess? If not now, when? My entire point being that at some point you have to start fixing the things that need fixing so that you can be more effective and efficient in managing the environment.
All that being said, I don't have a solution for you other than to suggest, again, that you use Group Policy to accomplish this.