Well I will admit that it takes some specialist tools. I have a program called a spatial filter. You can get them and I think (or so some people have alluded to) photoshop has some settings in it to do something like this. I wrote the program that I use - its very hard to explain how it works tho, or how to use it. If you know about Fourier Transforms then its easy else it would be hard work.

But if you want to send me any maps that need fixing then I could process them and send them back. What the program does is analyze the image and work out where certain patterns are. I told it to look for 45 deg lines and then it wipes them out. Since in this case the grid and most of the map detail is not in that pattern then it leaves it alone. The only problematic area is the coast top left where its also at 45 deg.

So if you still have the gray mask bit without the grid, text, coast or lines and just have the base floor then I could process it with no changes to the detail layers at all and then you could substitute them back afterwards.

Attached is a pic of the worst part of the map processed. The text has some background lightness issues and the green and blue fo the coast has transposed a little but if the text is on a different layer then the only effect that you would have is the coast and sea transposing. Since your sea is one color then you can fix that and the land color change is pretty minimal I think. Much better than the big lines on it.