A priest is an awesome BG and PvP healer for the paladin team, due to the stonr disc bubbles, they will pretty much ensure you never need heals as a paladin team. the only issue, is that with a paladin team, you are ALWAYS running around in BGs and killing people, and a priest healer is maybe the only healer who can keep up, besides a druid. I tried a a shaman, but never got far because of the lack of on-the-run heals. A priest has a great mix of buffs and stuff. Also, you could always stop as long as u needed to penance your low HP paladin and then keep running.

The only downside, is being kited like CRAZY. The ret pally + Dk thing works so well because of the DK slows it brings. without it, the team may be a little gimped, but then again if you are chasing someone in a BG, you can usually just find someone else and destroy them instead.