First the why is this:
Some people have low self-esteem and look for ways to belittle other people as a method propping up their own self-concept. By saying in effect "I'm better than you because I've been here longer/seen that discussion already/already argued that to death." they are making themselves feel good.
Complaining that the question has shown up before makes the person aware of this and rebukes them for not checking first.
I don't think anyone should ever be rebuked for asking a question. Even if it has been asked a million times before. Have you ever trained someone to do a difficult task at work? At which point do you start "rebuking" them for asking the same question too many times?
Furthermore, it is morally wrong to rebuke someone for not doing something that they are not capable of doing in the first place (searching old threads)
But there's really no way to do that without, in actuality, being insulting. At best you can hide that consequence deep enough in implication that some people won't notice it.
First, I doubt there is anyone on these boards more skilled in handing out verbal beat-downs than myself, and I have to completely disagree with you on this. Being polite is not impossible, it is only more difficult for some of us than others.
For example:
you might post a thread asking about the prevalence of gamer girls.
I might say " Hi WotS. Did you know this topic has been discussed before? If you would like to read those discussions, here are the links [insert links found via searching]

"
I might say " This topic comes up every few months and it usually results in people saying things like [insert various comments I remember from previous threads]

"
There is no reason for me to say things that imply I think that I am in some way "better than you" because I simply happen to have seen similar discussions in the past.
Really though, the problem is that the impersonality of text communication lends itself to perceived insults and supposed affronts. Therefore, we should always go the extra mile to be as polite as possible. Make generous use of the "

" and don't make accusatory statements. Couch your language with phrases like "I think" and "maybe" and "perhaps." Be careful not to act aloof or superior. Say “we” rather than “you,” if at all possible.
Being condescending, aloof, intimidating, accusatory, presumptive, and belligerent are tactics you use when you are looking for a fight. They shouldn't be used here.
And, of course, if we don't have anything nice to say, we probably shouldn't say anything at all.