Even though, Joseph McCarthy's efforts were perfectly in line with Truman's "Loyalty Order" -- Executive Order 9835 -- as well as the public disclosures of the Venona project (in 1995).
Why has the mainstream narrative continued to regard McCarthyism as "making accusations of subversion or treason without proper regard for evidence"?
Note: The Venona materials revealed that the communist infiltration of the U.S. government was far greater than even McCarthy had suspected.
Why has the mainstream narrative continued to regard McCarthyism as "making accusations of subversion or treason without proper regard for evidence"?
Because there is no evidence that McCarthy was finding actual communist infiltrators by anything more than accident. Note that many of the people at whom he was looking were not in the government, so Venona's identification of people in the government wouldn't apply to them.
Wikipedia has a list of people identified by the Venona project. I don't have a similar list of McCarthy targets against whom to compare, but I did a quick sanity check of Joel Barr, Alice Barrows, and Theodore Bayer. These are the first three confirmed spies on the list, and none of them had anything to do with Senator McCarthy or the House Un-American Activities Committee.
As others have noted, McCarthy's activities did more to discredit Communist hunting than to promote it. By basing his investigations on slurs and innuendo, he made it look like more serious organizations like the Subversive Activities Control Board were also engaged in witch hunts. One critic went so far as to accuse McCarthy of voting the Communist Party line in the Senate.
McCarthy gave Communist hunting a bad name by the way that he approached it. He was rejected by anti-Communist liberal Democrats like author Rex Stout and eventually by many Republicans. He is best viewed as an example of how not to pursue an investigation or promote a cause.
TL;DR McCarthy is regarding as "making accusations of subversion or treason without proper regard for evidence" because that is what he did. It was other groups that were doing the hard work of finding actual Communists and collecting prosecutable evidence against them.
The OP is correct in one instance, the Venona program revealed extensive, effective efforts by the Soviets to infiltrate American institutions and academia:
When the VENONA project was finally ended in 1980 many thousands of cables collected during the 1930s and 1940s were still unread, and slightly more than half of the 349 persons given cryptonyms by the KGB remained unknown. But even those identified included agents seeded throughout the federal government in Washington, in large corporations and universities, on newspapers and magazines, and in the principal laboratories which built the first atomic bombs. ...The 349 cryptonyms extracted from the VENONA traffic—most standing for agents or “trusted contacts” but some referring only to targets of interest—may be matched by as many more in the unread traffic, and the GRU cables of the same period, still almost entirely unread, might contain as many more again.
In the The Plot Thickens by Thomas Powers talks about the interplay between McCarthy's recklessness, the FBI against the backdrop of the treasonous Alger Hiss and the efforts of Democrats to protect him:
As a spy hunter McCarthy was a complete failure. His elastic numbers, never the same two days running, were much derided at the time; he never found even a single genuine Communist in the government; none of those he named recklessly during his hour on the stage was ever proved to have been a spy; and none of them appear in the VENONA traffic or the documents published by Weinstein and others. A rough-and-tumble demagogue of a certain raffish charm, McCarthy never really understood the chapter and verse of Communist spying, much less the subtler play of left-right ideological struggles, which tempted many liberals of the time to deny overheated right-wing charges of subversion with counterclaims that the “Red Menace” was all being trumped up by the FBI.
In the heat of the moment, when Chambers’s charges had first become public, leading officials like Dean Acheson and President Truman had both defended Hiss, a position they would soon know enough to regret. But those regrets they kept mainly to themselves, and Hiss posed for years as the archetype of persons unjustly charged in what was criticized as a Republican witch hunt. Still, despite McCarthy’s failure to back up his charges he managed to flourish for a time in a climate of suspicion that Hiss wasn’t the only Soviet spy with a claque of defenders and that the government was hiding something. At the same time, counterintelligence professionals knew McCarthy was thrashing around in the dark, but many of them also knew directly or through the grapevine that the FBI was in fact trying to identify hundreds of cryptonyms.
Ronald Radosh, an expert on the subject of Communist infiltration into America, wrote an excellent review of Morgan's Reds: McCarthyism in Twentieth-Century America in the Washington Post that covered off of the same topics you mentioned: re-evaluating McCarthy in light of the Venona program.
A latecomer to the anticommunist cause, McCarthy used a lag in perception about communists in government to engage in the kind of scattershot and irresponsible charges that made him headline news. He sometimes had a valid case about people who presented serious security risks still holding places in government, but he ruined it by overstating and by changing the numbers of those who supposedly still were implanted. His facts were wrong, but his timing -- coming after the exposure of Alger Hiss's treachery and the fall of Nationalist China -- was perfect. Rather than really being concerned with improving security, McCarthy was more interested in discrediting the Truman administration and using his investigations to gain political influence and power. There were no spies left in the State Department by February of 1950, although security could have been tightened. But McCarthy did not study carefully what files he had obtained, nor did he cull his list. Instead, as Morgan writes, he concealed sources and sought to overwhelm the Senate "with the bogus momentousness of his findings."
The reason is not that McCarthy was wrong, it's because he was right.