If fuser didnt fix it, chances are the paper is going in crooked, exiting crooked, paper is very humid (paper problems). Fix those issues with a good tech and problems should go away.
WE had this problem and were told it was unheard of.
They replaced the doors and the fuser, see if you get different effect if you output to the central tray or bottom tray (to eliminate if its something with the rollers).
Hopefully that will fix it.
For us it wasnt and the UK company who are outsourced to fix it refused to replace or do anything else leaving us with the problem, we managed to minimise it by replacing the fuser and printing to the centre bottom tray rather than the centre tray.
We've had our Phaser 7800 for just over a year now. Since day one however, it has left crease marks along pages as if the rollers somewhere in the machine are pressing too hard on the paper. Is this fixable? Thank you.