So, I did a test for Deadmines today. Here's how it went:

*note that there was no rested xp on any characters.

4 lvl 20's + lvl 70 warrior: 26,000 xp / hr
4 lvl 20's + lvl 30 paladin: 8,500 xp / hr
4 lvl 21's (they dinged) + lvl 70 warrior: 20,000 xp/hr

For the first 2 runs, I skipped all loot except bosses. The last run I felt I could loot due to the fact that I proved my point.

Now, I'm wondering when the speed of using the warrior will stop being such an advantage compared to slowly going through with a paladin. I figure that I can cruise right through SM and get up to lvl 45-50 before I start to notice.