My 3.0 half-celestial paladin rocked. Being able to pull off massive bonuses to Divine Might and Divine Grace more than made up for losing some HP and a few measly points off of Smite Evil.
Also, paladins don't have any dump stats, and so they benefit from everything. I suspect that only a cleric can really match the results you get from a paladin with high stats across the board.
In 3.0, Smite Evil was a one-shot deal, while the mount and just about all paladin spells but Holy Sword were completely dismissable at high levels. They've improved smiting and slightly improved the mount, but nerfed the hell out of Holy Sword. They also inexplicably nerfed the turning ability, making the penalty 3 levels instead of two. So the best use of your turning attempts now are a) smashing hordes of wimpy undead wooks or b) converting them into divine feats. Turning isn't going to work on anything that would be a real threat to your paladin.
Lay on Hands and Smite Evil are the main reasons to take a paladin to high levels, now. The mount will still die in nothing flat if it's targetted, and paladin magic is basically garbage (the 1/2 caster level thing certianly doesn't help) -- it'll work okay if you can get a prayer bead of karma, but otherwise it's a waste of time.
The Divine Champion PrC from the FRCS is a very good PrC for a Paladin to multi-class into, since it's also loaded with abilities based on charisma, including a smite ability that works on anything that doesn't worship the champion's god.