Yup, it occurs with all fonts. Not with shapes, their outline prints fine.
Since my last post we figured out the problem (but no solution yet...). Apparantly the printer prints all the outlines around text to thick.
e.g. a 1 points line will fill the page, while a 0.000003pt line will look like a 1pt line before...
Obviously we can't be changing all the artwork of all our clients, so we are still looking (and fighting with xerox) to get a proper solution.