I'm VERY happy with how the Pally/Mage/Mage team turned out and all along the way I never had much trouble with needing heals. I had a priest with me much of the time so I was able to go Prot, but in many situations I found myself 3 boxing instead of running with my girlfriends pally...

The long and short of it is the extra healer was a waste unless we were REALLY pushing content. Spec a paladin Holy enough to get so with concentration aura you can't be interupted on heals and you are golden.