As a mainly Paladin player, I think you are overating our 'heal' abilities. Paladin's are still fighter/tank class. Our heals up to level 22 (my current so all I know for certain), are strictly minor. LayingOfHands is a great heal, but it's strictly for emergencies - 30 minute resuse timer, and our other heals are trivial compared to a real healer.
Fighter/Priest is pretty much the only duo that works. Given scout, scout/priest may be the best of a bad bunch - templars get to wear heavy armour, so they can tank a bit ( I Have a 20 templar alt too - I've had great fun tanking in a group of 3 healers a scout and a mage, but not terribly efficient).
Otherwise why not open up your duo to others? Its a social game after all. The real minimum group is Fighter/Priest/Damage, where damage can be either of the other two classes. As you will hopefully be playing with more than just the two of you, I'd suggest picking a type that appeals to you, rather than just being "useful".
Edited, Mon Mar 21 16:10:30 2005 by antrygwindrose