Well the coated paper may be a problem...it would be on an office grade machine but sounds like it's just bad engineering. You could test run the same job but on 20lb bond paper. If they still "break" just as quick then it's not the paper.
Seems to me that the only problem is that you guys aren't getting a different machine or making enough stink about it. Are you paying for the drums or are you guys on a plan and Xerox covers them. Still, it would be annoying swapping parts out all the time.
Not sure what type the 5000 drums are but on my stuff you can wipe the drums with alcohol. Maybe the coated paper is leaving a film and effecting quality, charge, and transfer. Maybe wiping and removing film residue would help...you'd need to confirm that with Xerox though.
I have had coated card stock mess up drums and fusers though.