From the SRD: "Detect Evil: At will, the paladin can detect evil as a spell-like ability. This ability duplicates the effects of the spell detect evil. "
Then: "Use spell-like ability [Standard][AoO: Yes]
casting a spell in that it requires concentration and provokes attacks of opportunity. Spell-like abilities can be disrupted. If a character's concentration is broken, the attempt to use the ability fails, but the attempt counts as if the character had used the ability. The casting time of a spell-like ability is 1 action, making its use a standard action, unless the ability description notes otherwise.
A character may attempt to use a spell-like ability on the defensive, just as with a spell. If the Concentration check (DC 15) fails, the character can't use the ability, but the attempt counts as if the character had used the ability. "
Remember also that the Paladin's Detect Evil ability is only a first level spell ability, fairly easy to foil, if one so desires. The concentration would be somewhat obvious, IMHO, especially since it would incur an AoO to use the ability in combat (and then spend 18 seconds after activating the ability sifting through the psychic debris about you). A succesful bluff check might cover this, however. Remember also two more things: first, that thick walls and other things block detect abilities and second, that being evil isn't a license to be killed. Note, for example, that at least half of the rulers in Greyhawk are evil in alignment. That doesn't mean they're evil dictators, necessarily...just that they're ruthless bastards when crossed, or would be glad to do someone dirt to advance their position. Evil in your heart is not the same as having committed a punishable crime. Evil people may even be redemable...but not if they're dead.