If you are going to reroll if low anyway, why not roll 2d20 and take the better of the two? It might even make sense as a racial characteristic. Elves have excellent senses, so when making Search, Spot, and Listen checks they roll 2d20 and take the better of the two. This also has the advantage that the rest of the players do not know whether he failed because it was not there to be found or because he rolled low on both rolls. If he fails the first time and you ask the elven character to roll again it is more or less a bright light to the other players that there is in fact something to be found there - if they can think of a non-metagame reason for their characters to also take notice. If the elven PC rolls 2 d20s when searching - just as they normally would in such a system - then there is no spot light effect.
Of course, there are likely problems with this that I am overlooking.