your GSM settings might be wrong for it. The fusers base setting is based on the GSM rating for the paper selected. If you input cover stock, for example, and say its text weight and turn up the fuser temp to max it will still not be enough, for the fuser setting is low enough to fuse the text weight toner but not the cover weight. You said the front edge (right?) of the paper is rubbing off, well that is probably the fuser trying to reacquire its optimal temprature after the last paper went through and hadn't reached it when the paper arives.
Try selecting a thicker paper setting.
Black toner is rubbing off on my Xerox Phaser 7500. This happens only on certain areas of the paper.
For example, I repeat the same image 4 times over the paper (SRA3 300gsm HiQ Gloss Paper from Xerox) The black bits on the the first two images rubs off, the rest doesn't.
I have tried everything:
Different paper suppliers
Callibrated for paper
Changed toner settings
Changed toner temp settings.
Different paper settings (Heavy card stock, Heavy glossy, Extra Thick Plain, whatever)
Fuser life is at 81% remaining.