A long soaking
I forgot to wash off my battlemap and it sat for about a full month one time with a mix of blue, green and black vis-a-vis wall and door markings. I tried to just wash it off and it didn't budge. One of the colors did come off with some effort (either blue or green, don't remember now). The black and one of the other colors was left.
I did something wierd, and wound up soaking it in my bathtub (just plain luke-warm water) to see if it would loosen the colors. It probably soaked for about 15 minutes, and by the time I got back to it, the entire map was beginning to get better. With a rag I was able to remove about 90% of the marks, but some were still hard to get off.
The downside of this was that the color from the ink got onto the backside of map while it was in the tub. After more attempts at soaking and drying, most of it has now come clean. My main problem now appears to be a few smal green marks on top of the division lines. Soaking hasn't helped those at all.
Hopefully, there is no long-term damage from such extended soakings. I've seen no problems yet. However, I'm now a lot more careful to always wash it after use.