Thanks for your suggestions. I think jader and mmcarn are right, it is a driver issue or a failing memory issue - maybe both?
The printer works fine from Windows, using the PCL-driver from OKI's website. No problems with large PDF and graphics files. For Linux I now use the PPD-file from the Windows-driver. Simple files seem to print fine from Linux, but for complicated files (larger files, pdf-files, files with lots of graphics) very often print out as garbage. Sometimes I can print a large file ok, if I print it one page at a time, but if I try to print it all in one go, I get garbage. I have tried to lower the resolution, but with little, if any, effect.
I have not been able to find "memory protection" option - where should I look for that? In the PPD-file or in the printer settings?