Probably about 20% to 30% of human beings are Evil as D&D defines it. You don't have to be breaking the law to be evil. You just have to be willing to screw over other people for your own benefit. The innkeeper who waters down his drinks, the sailor who makes his mates clean up his messes, the petty beauracrat who takes enormous pleasure in tormenting people what what little power he has.... these are the mundane, everyday evils of life.
A paladin can't just go around smiting these people either. Quite apart from them not having committed any (large) crimes, most of them are probably redeemable. Few people set out in life to be a jerk. A paladin has to reach out to these people via word and deed, to present them with an example of a better way to live.
As someone said, it must be difficult to be a paladin without becoming a cynic. You constantly see how low so much of humanity sinks.
The house rule I advocate is relaxing the restriction against associating with evil. I'd say that if a paladin is actively trying to reach and and reform someone, it's okay for him to associate with evil. Whether that be sailing on a ship with evil sailors or drinking in a tavern with an evil barkeeper.
Now of course, the vast majority of evil the paladin senses is going to be faint evil. If he senses something stronger than that, it should definitely get his attention. Whether it's an undead, a priest of an evil god, or just a really high level evil NPC, he knows it's something he needs to investigate.
The the DM who started this thread, I say let your player use Detect Evil as much as he wants. Tell him that on average, 30% of the people he detects are evil and you're only going to mention the ping on a specific character if it seems relevant or if he gets something stronger than faint evil.
Shouldn't cause too many problems.