A note: this is long.
Elwro- if you've gained the butcher of hommlet title, he'll attack. And if you've messed with his family (his parents in the SW-most farm) or with Otis, his brother.
DarkUnderlord-
I'm really rather curious as to the details of your party. By class features, paladins have good hps, good saves (assuming a charisma bonus), and the best base attack bones (1:1 progression), no restrictions on weapons/armor, and moderate healing abilities
Aside from the 'obscure knowledge' monsters like the puddings, and situations where you don't have holy/silver/cold weapons to breach damage reduction, you should be fairly well set for combat (assuming the strength scores aren't low- less than 14 is usually a problem).
Because, frankly, Llamagod is wrong. All tank parties can do rather well. The game can be difficult with all non fighter types, but with all tanks, most battles should be fairly straightforward. Rogues aren't necessary at all, paladins give you some of the buff/healing that clerics or bards do (and better combat abilities). Paladins are a little less effective than barbarians or fighters, but make up for it in the after action healing, usually better than rangers in combat, are less specialized than druids or monks (both can be spectacular, but if you're not really on the ball with them, then tend to blow) and while you don't have the range of a wiz/sorcerer, a warrior type with a reach weapon and cleave/great cleave can rip through minions as easily as a fireball.
You're only major problem will be missing out on item creation. Which is big for getting past DR.
Real problems with character building in TOEE. (in general, not necessarily for all paladin parties.)
1) bows/missile weapons in general. These kinda blow. the lack of mighty bows in particular can cause real problems, low damage rolls can effectively make shooting meaningless.... up until the point you have a character that can start enchanting things
with frost/shock/flaming/holy (and I mean stacking them all), which requires a cleric with the good domain, and a wizard (though a druid or sorcerer can do in a pinch) Three feats are pretty much required too, point blank shot, precise shot and rapid shot (for bows anyway). Without precise shot, assume you'll be hitting only on 20s.
2) good magical weapons (and in particular, good magical weapons that your people can focus in) If you don't have item creation, you're stuck with the few good weapons that you find. And there aren't many, and some are hidden/ near inaccesible.
3) feats. You can only take so many, and some, frankly, aren't good. This is a D&D issue rather than one specific to TOEE. Yeah some sound cool. But how many times are you going to use blindfighting? Improved trip is great, until 75% of your foes are large, high strength creatures. bonus to skills can be quite useful... but most of the game is combat. Feat chains that lead to things like whirlwind sound all cool and uber... but how many times will you really use it? great cleave is much easier to get, and can be just as devastaing. Power attack, if nothing else, you'll need it to get cleave. And it can also be useful to put the smack down on things- particularly with two handed weapons- the kings of 3.5 edition weaponry. You might even be able to breach DR the hard way.
Wizards/clerics- item creation feats. These cut the difficulty of the end game in half (if you make the weapons right- elemental effects and holy). Don't worry about much except for arms/armor and wondrous items (for the stat boosters). Maybe wands or potions for the cleric/druid/bard. And remember wizards trump sorcerers here. 3 bonus feats, and more than a paltry handful of spells known. And scrolls can easily make up for the loss of a few castings/day particularly if you load up on the buffs/miscellaneous spells (knock, for the few locked things that are really high DC)
But, as a side note. Craft arms and armor isn't really useful until 9th/10th level and you can put frost/shock/holy on things.. don't waste the XP too early on.
4) ah, a big one. party size. 4 is best. After that, XP gets spread around too much, and leveling becomes an issue. For example, a full party (5 pcs, 3 npcs) will probably be only 3rd level when they reach the grand melee in the guard tower. (I was, my first time through the game). A four person party will be about 5th or 6th. This is D&D.
Level > numbers
By a whole hell of a lot. More feats, more hps, higher level & more spells, better chances to hit. And you the items you've found/bought/made will be focused, and not spread thin... which is important, because the second most important thing in D&D after your level is your gear. then stats (& hp), then class, then feats, then skills. (At least, assuming a combat heavy environment like TOEE)