I think the problem isn't defining "holy" but defining "warrior". The paladin works outside the standard state-based military hierarchy because they can't offer the sort of loyalty expected of a soldier of the state. Instead they generally serve in a military wing of a religious organization of their deity (temple/priest guards and the Knights Templar come to mind) if they're not a variant of the knight errant (I think JdA falls into this category - she did lead an army, but she didn't rise through the ranks or start with a noble rank IIRC).