I've got a good geared prot paladin and DK, and from my experience, i boost upto 55 with the paladin, and with the DK from that point. Simple reason for this is that below 55 I can't effectively get my diseases up on mobs, because they die before i did icy touch & plague strike, so i can't pestilence (could do just 1 disease, but meh). I only tried -55 in scholomance on DK though, and I often had close fights because I got silenced all the time, and couldnt keep my diseases up to be able to heal myself with plague strike.

Paladin has np with this with seal of light. Maybe at lower levels than scholo DK has enough healing from the 2% from blood aura. Haven't tested that yet. but beyond lvl 55 (aka ramparts time) DK is definitely my preferred choice. (dk is tanking blood spec btw)