Ok, I think I located the problem.

When plotting drawings (with paperspace) we use a heading with the company logo, address, phone number,.... 

The heading is added in paperspace.

The text in the heading is mostly black with a few letters in a beige tint.

It looks like the color from that part of the heading somehow "bleeds trough" to the drawing for some strange reason.

When plotting with the heading the problem appears.

When plotting without the heading the problem goes away.

Any ideas on how to fix it other than removing the heading?

UPDATE: Could it be a issue with the printer? 

Its extremely odd only the grey colors are affected. It almost as if the autocad or the printer takes its info from the header text and applies it to the entire sheet.