For what amounts to an etymological question, this one is surprisingly complex...

The original version of this story is that it was a term used internally during the Second World War by the US Government to brand American veterans of the Spanish Civil War, signifying their supposed political unreliability due to their connections with communism. The veterans and their allies, when they found out about it, used it to demonstrate the very ridiculousness you point to - in the words of British volunteer Bernard Knox (who wrote that he encountered the phrase when applying for a job at Yale after the war,), 'if you were not premature, what sort of anti-fascist were you supposed to be? A punctual anti-fascist?'. In other words, the ex-volunteers were being victimised because they had recognised the dangers of fascism and sought to do something about it before the US Government had.

The term has grown more and more popular ever since, even outside the North American context where it originated, as a general label for the discrimination and suspicion faced by former Spanish Civil War volunteers in their home countries. This actually has its own issues, as the use of this label as a general term obscures quite significant differences across contexts - a topic I happen to have published on in the past - but even in a purely American context, the term has proven surprisingly controversial. About twenty years ago, two scholars (John Haynes and Harvey Klehr, both known for their distinct lack of sympathy towards communism) took Peter Carroll (the most prominent historian of American involvement in the Spanish Civil War, and considerably more sympathetic to communism) to task for alleged 'scholarly malpractice' in his pushing the narrative above. Haynes and Klehr cast doubt on these origins of the term, pointing out that no known US Government document actually uses these words, and that evidence rests on somewhat sketchy oral testimony given decades later. A lot of this controversy hinges around the version given by veteran Milton Wolff as described in Carroll's 1994 book:

Inquiries about the unusual delay brought mystified responses, until Wolff mentioned to a clerk that they had been in Spain. "Oh, that's a different story!" exclaimed the friendly sergeant, who finally found their records in a special file. A few nights later, Wolff and Cook sneaked into the office and read their papers. Printed on the corners were the letters "P.A." The next day, a clerk explained the initials: "premature antifascists." Thus they discovered a euphemism that would become part of anti-Communist rhetoric of the next decade. Service in the Spanish war qualified the Lincolns for that honor.

Carroll later reinterviewed Wolff to confirm the story, but Wolff gave a slightly different version:

My source for that reference was my interviews with Wolff himself. As he told me the story about ten years ago, he and another Lincoln veteran, Gerry Cook, were detained at Camp Dix (New Jersey) in June 1942, soon after they had enlisted in the U.S. army. To their dismay, other recruits were routinely being shifted to other camps for basic training, but they remained unassigned. Frustrated by this situation, they entered the camp's office at night and found their names on cards with the initials PA. The next day, they confronted a clerk with that information, and he supposedly said something like "oh, that's why you're not being shipped out." Prompted by the recent flurry of interest in this matter, I reinterviewed Wolff yesterday (May 24, 2000) about this issue. He now told the story differently. Only Cook actually broke into the office, so that Wolff could not, in fact, testify to the authenticity of the PA story. But he was sure that something in their records prompted the clerk's response the next day.

Haynes and Klehr concluded that the term was in fact the invention of the Spanish veterans themselves, used as a sardonic self-label and intended (in the authors' view) to disguise their initial opposition to the war before the invasion of the USSR, and that the narrative that it was a government term only gained traction in the 1970s. Carroll was, needless to say, a bit miffed by these accusations, and did some more work to try and substantiate the original story through contemporary documents (noting, however, that since most army personnel records were accidentally destroyed by fire in 1975, and FBI records were not fully public, it was hardly all that telling that no such source had yet been found). In 2003, Carroll did indeed locate a wartime use of the phrase by a government official - a US congressman, John Coffee, giving a speech in 1945, during which he said:

There is, of course, no honor high enough for those few thousand gallant American men and boys (they call them premature anti-fascists in some nasty Washington circles today!) who made their way to Spain and fought and suffered in the ranks of the Abraham Lincoln Brigade.

This, you'll note, is hardly a smoking gun - it's once again hearsay coming from the mouth of someone sympathetic to the former volunteers, but in a way that doesn't fit neatly with the narrative of deliberate, later distortion put forward by Haynes and Klehr. Carroll's efforts to locate the origins of the phrase were recently taken a step further by another scholar working with the benefit of subsequent mass digitisation (see thread here), who found similar uses dating to much earlier in the war (at least 1943). Yet equally, there is still no strong case for a government origin to the term - all the early usages that I've seen point to the term having currency in left-wing circles, but not necessarily anywhere else.

At this point, I think the etymology of the term has consumed far more historical attention than is really warranted. The reality of the discrimination itself - no matter how it was labelled - is well established in the American context, both during the war and then into the 'Red Scares' of the early Cold War period. As a result, that the argument has been so long and heated only really makes sense when viewed as an extension of the wider ideological battle that was still being fought by Carroll, Klehr and Harvey into the new millennium, in which the specific credibility of communist and anti-communist narratives was vital. For historians interested in what actually happened and why, it's another of many distractions relating to the Spanish Civil War born in Cold War-era obsessions yet somehow still have currency today.