The Royal Caravan
Paladins Without Alignment
The paladin's code of conduct becomes "A paladin's code requires that she respect legitimate authority, act with honor (not lying, not cheating, not using poison, and so forth), help those in need (provided they do not use the help in a way that betrays any of the paladin's loyalties), and punish those who harm or threaten innocents." Remove the Associates section under the code of conduct. A paladin must have a loyalty to the concept of good, and most paladins also have loyalty to a deity. Creatures whose loyalties are in opposition to the paladin's gain no benefit from the paladin's aura of justice ability.
The paladin's smite evil ability works against any foe whose loyalties are directly contrary to the paladin's highest loyalty. She can also recover one use of smite if she accidentally smites an invalid target. She can do this a number of times per day equal to her maximum uses per day of smite. This means the paladin isn't punished for having to guess, but she also can't use her smite class feature on every opponent as a de facto loyalty detector. If the paladin's highest loyalty is to good, she can smite foes with a loyalty to evil, but if her highest loyalty is to her king, her smite might instead apply to foes with loyalties to the jealous baron's rebellion. The GM has the final say on how the ability works, since only the GM knows the NPCs' true loyalties—a mercenary who works for a cause might not have a loyalty to that cause, for example. The GM can decide to simply have smite work only on foes with a loyalty to evil, or to require the paladin's highest loyalty be to the concept of good.
Detect evil (and similar spells) works on those who are loyal to evil or any concept that is close enough to evil.