Actually, gaydar has been held up with statistically significant results, but the effect isn't very strong; people are only slightly more likely than chance to be correct in their hunches (so if the experiment is structured so that the pictures people are looking at are 50-50 straight-gay they might get perhaps 57% right). The effect does not seem to be contingent on how long someone looks at the pictures, so people can tell at a glance.
That's just looking at pictures, which is only part of it. Obviously there are cues other than the actual facial form and whatnot--certain mannerisms which tend to be adopted, certain patterns of speech. Of course, it's unclear whether these are actually an inherent part of being gay or something affected (probably often unconsciously), but they do tend to be present in most gay men.
Lesbians are a whole different story, and in my experience much more difficult to pick out outside of those who make their sexuality plain intentionally. But certainly there are gay men who are not obviously gay at all as well.