I think nowadays it is easy to listen to others speak who are native speakers. For example, due to television, I have some practice listening to what (some) British people sound like. Similarly, due to television, I have some practice listening to what (some American) Southerners sound like. You can imagine that before the days that it was possible to record audio, we might have had no idea what other native speakers sounded like. In fact, it seems plausible that in those times, people could have mistaken native speakers from other place for nonnative speakers because they didn't sound the same ("they don't sound like me").
Again, because of media, I have practice listening to nonnative accents too, like Chinese and Russian. So, when I hear them spoken in real life I recognize them instantly. I know that those people do not come from places where English is spoken "natively". So even if a person with a nonnative accent had impeccable grammar skills, because I have practice identifying accents that are not native, I would identify the person as a nonnative speaker.
I guess I forgot the address the first part of your question. I doubt there is a "most important thing". The two big clues that I can think of are accent (in the sense that it doesn't match one of the well-known ones, per se), and grammar. Now, having poor grammar doesn't imply that you are not a native speaker, as there are plenty of native speakers with poor grammar (myself included). But I think there are few distinct patterns that might serves as hints, like the lack of articles.