I switched my Main over to the Monk Tank when I came back a couple months ago. He was really OP leveling up. Even without Heirlooms (Cross server wasnt available yet), I was still doing better DPS than most people decked out in them. After spending some time with other tanks on varying difficulties of SoO though, I still find that I think the Paladin is a better Tank. Most paladins I run up against do about 10k healing/ps more than I do, per fight, on average. Take less spike damage than other tanks. Have better CD's than most classes and lastly.. the Paladins Im around typically do more DPS than I do. I would just think I suck at my rotation or something, but I usually out DPS Warrior, DK and Druid Tanks in comparison. Though, none of the tanks are necessarily shitty in regards to each other. I just think the Paladin has the upper hand.
Oh, and yea... playing a DK tank when they came out was good times.