Actually, in technical terms I have to disagree.
It's a spell-like ability which means that there is concentration involved. However, if the Paladin is just standing around, it is not obvious. In fact it most probably looks like he's doing a scan of the area during the first round. This is pretty much the behaviour of any proficient fighter type being on guard and checking for threats. If the Paladin does not sense evil, the attempt's all over. It's only if the Paladin persists with this behaviour by focusing on individuals that people will feel the Gaze of the Paladin and like Hypersmurf says, it then becomes pretty obvious.
As well, if he tries to do it while others are interacting with him, it could lead to interesting and obvious results.
However, as a person who enjoys playing the Paladin, I'm a little disturbed by your nerfing his ability by letting all those nobles have a way of knocking out his radar - most unsportsmanlike. Now does the Paladin go around poisoning and backstabbing all your bad guys? No. So let him have his fun with his little ability.
In all seriousness though, sometimes the best thing to do with a Player who has to stare down every square inch of your, dungeon, city or heaven forbid wilderness is to take them aside and give them a chat. Tell them that it's getting annoying. However, if you want to make them feel special, tell them you'll give them a wink if they start feeling uneasy - that evil is possibly present. This saves a lot of time and it will remind them that a Paladin can and should be doing more things than using their detect evil ability.
Alternatively, if they are in a large confined area - a dungeon - tell them that they sense a feint evil all over the place - see the lingering table on p193 of the PHB for details.
Best Regards
Herremann the Wise