I know this is a bit late in answering this forum but I have been experiencing the same issue. The way I fixed it was to go to the Advanced Options tab in my printer properties (we have an HP T1100) and there is an option under Printer Features for Max. Application Resolution. Instead of the default I chose 300. This, for some reason, got rid of my strange lines.
I also learned that if you choose to "Show Preview before Printing" the previews actually show the mysterious lines. I kept changing settings until I found the change above, where the extra lines disappeared in the preview.
I don't know if this helps others but it solved my problem with this particular map!
This seems to work! I found similar settings in the advanced settings for our Konica Minolta C652 Series. My only concern is that we send both hard copies and digital copies of reports / maps to clients. If our clients print additional copies, that line will surely show up again.