I suspect your getting ink transfer from the letterhead into the inner workings of your HP laserjet. Possibly via the transfer roller.
It could be that the ink your letterhead has been printed with is not sufficiently heat resistant to prevent it transferring to the internal components of your HP laserjet. It needs to be able to cope with a good 200 degrees.
It may also be due to a reaction between the letterhead ink and the resin in the HP toner.