That sounds like it is a LOT of work you have in front of you, Vigilus. My suggestion (from a NON P-shopper) would be to place two marks (one in each corner across where two of your sheets meet) in a color that is NOT used in the map, and then scan them into PS. Once there you can use those marks to ensure that they are properly aligned. Once that is done I believe PS will allow you to select JUST that color and remove it. I believe that that should do it.
Maybe a 'shopper will be more specific, but in the meantime I believe that that should do it.