Just a few thoughts, those marks sure do look like a bad toner cart. Are you saying the same marks were there before replacing toner? Do the marks move at all? You have replaced everything that would cause quality issues. If it was a dirty laser you would have light areas. Stop paper before fuser to see if marks are there to rule out fuser?