Intermittent Printing issues with HP laserjet 4200/4250 printers

I would like to know if anyone else has also experienced this. We have an office that uses about 6-7 4200 or 4250 laserjet printers. Here are the following issues that we have with the majority of them:

1.) intermittently prints words bunched to gether (on random pages).
2.) intermittently prints a document but removes underlines from certain parts.

There are some other things, but its mostly documents which show up in print preview perfectly fine, not printing that way on the printer. We have been tackling this for a few months and have literally tried everything. Here is a summary of what we have done so far:

Computer:
-Rebuilt profile
-Rebuilt computer
-Reinstalled and Reimpaired office (although these symptoms affect any application that prints).
- bought a brand new computer
- fully updated OS and firmware/bios

Network
- Print through printserver
- Tried through alternate print server
- Tried through direct tcp/ip connection
- swapped out ethernet cable from computers to the wall
-Swapped out cables from patch panels to the switch
- tried different ports on switch, and different drops on wall

Printer
- upgraded to latest firmware
- Bought new printer (p4014) to replace 4200 and the same things keep happening!
- Tried PCL6 drivers (this causes PCLX error pages to print on many occassion which makes the problem even worse)
- PCL5e, SAP is what they are currently on and are experiencing the problem.

We are looking at going with a different company all together. Has anyone ever seen or dealt with this on this type of scale? Issue is effecting many people in the office. It happens intermittantly and you can not recreate the problem at will.

Thanks