We definitely do not need cleaves in the middle of effing combat. That's one of the major reasons for intimidate I thought, was so the hellion has a much, much better chance of being the one to get the first hit(CLEAVE) in. Cleave effing hurts, unless you have good armor, MP, and sanc/protection(which doesn't help if you're a darkie too, and there's lots of DvD) up, and even then it usually still does a decent amount of damage. Unless it's a merc/barb I guess, but I haven't really played many of those...1 to be exact.
IMO however, if the hellion doesn't start the fight with a cleave they are a bit weak. I'm not exactly saying they need a buff though...
And as far as the sanc vs. intimidate, intimidate wins hands down as far as getting the first hit, all you have to do is spam cleave xxx a few times and you'll get through if you're about the same level(even if you aren't a lot of the time) but sanc reduces damage. You can't really say one is better than the other, I love the sanctuary spell, but I've seen intimidate do some really helpful things(HQ raids/City raids) and if the paladin gets intimidated, that's it, they cant' keep spamming BoG xxx, they have to wait till it wears off. Never had a high-level hellion myself, the one I tried got to whatever level cleave is, I think veteran.
On a side note that doesn't really matter, I think I brought this up when I played my rather short-lived paladin, saying paladin>hellion.
Despite what the helpfile and all that says, IMHO the classes are not designed to be like mortal enemies, Paladins have one area of enemies they're GREAT at killing, where as Hellions can do pretty good against everyone. BTW getting cleaved twice in the same fight, and getting cleaved in the middle of a fight with someone/thing else really, really sucks. QQ.
To sum this up IMHTGO you just can't compare Paladins and Hellions, despite the OMFG MORTAL ENEMIES!!!! they're not designed like especially to fight each other(well paladins are, but Hellions aren't) this doesn't even matter, who wins a fight will almost always come down to the PLAYERS, how PREPARED the two people are, and a looooooot of LUCK.