I know this doesn't fulfil the 3rd edition detect evil flavour that well, but it would suit 4e better if detect evil was a perception/insight bonus rather than a power. Also, there should be options for non-lawful good paladins.
Grant paladins the following class feature.
Detect Enemy of the Cause
Choose up to 3 keywords, origins, or alignments. You may not choose the divine origin. You gain a +2 bonus to perception checks to detect creatures with these keywords, origins, or alignments, and to insight checks to see through the bluffs and disguises of these creatures.
I'm not sure about the name, so please tell me if you can think of a better one.