The full quote there is kind of taken out of context. I just went ahead and skimmed the first couple hundred pages of his book since they're available for free on Google Books.

Here is the full quote (any errors mine since I'm transcribing) -

One gratifying aspect of our rise to some prominence is that, for the first time in my memory, we, "our side", had captured a crucial word from the enemy. Other words, such as "liberal," had been originally identified with laissez-faire libertarians, but had been captured by left wing statists, forcing us in the 1940's to call ourselves rather feebly "true" or "classical" liberals. "Libertarians" in contrast, had long been simply a polite word for left wing anarchists, that is for anti-private property anarchists, either of the communist or syndicalist variety. But now we had taken it over, and more properly from the view of etymology; since we were proponents of individual liberty and therefore of the individual's right to his property.

Rothbard, pg 83

So he's making a couple claims here. First he claims that liberal was originally a free market word. That is demonstrably false. Liberal is a very wide political theory, not an economic theory. It did include a free-er market than 18th century conservatism, but Adam Smith himself was not a proponent of Laissez-Faire as it's promoted today. He was in favor of less regulations in comparison to Mercantilism, where the government tightly controlled the economy and picked winners by handing out monopolies and forming corporations. (Again, not the corporations you're familiar with today) The main thrust of Classical liberalism was very simple, that people have a set of inalienable rights that cannot be guaranteed by divine right monarchy. Thus they should be allowed to rule themselves, preferably by representative government. One of those rights was the right to property according to some theorists such as Locke. However another point of agreement was the Harm Principle, so while they may have agreed on your right to property, where those rights end is a matter of debate to this day. Basically you cannot hold your rights so sovereign they trample the rights of others. So Rothbard's assertion that "Liberal" was originally associated with free market ideology, as he was writing this around 1970, is false. By then free market ideology had been taken to an extreme by the Austrian School of economists. (That was around the mid 1800's so before he was even born.) Liberalism was always pro-state, the guys who wrote the Constitution were famously liberals.

His second point is very interesting to me and it goes to what you're saying. He claims "Libertarian" had, "long been simply a polite word for left wing anarchists..." But elsewhere in his book he went to great lengths to redefine communist movements in Mexico and other places as Libertarian. He gives no solid references to support this either.

The peasants of the world are not socialists or communists; instinctively, they are individualists and libertarians, consumed with a perfectly understandable passion to reclaim the right to own their lands.

Rothbard, pg 187

In 1970, and the 20 years before, the various communist movements were almost all reactionary to colonial states. So yes, they literally wanted their land back. That in no way means they wanted to administrate their land in a libertarian fashion. If you cross reference a list of communist parties and dates of independence you'll find that the majority of communist movements come from former Soviet states, China, and countries that gained independence from about 1960-1980. To say nothing of his general assertion towards what we would call, "the working class." In this light I don't think this is a good source for the claim that Libertarianism was a leftist ideology first. He's clearly writing from a perspective meant to convert people, not convey objective truth.

The third point, that they're more entitled to the word is just ridiculous. but they certainly have it now.

All of that said, I haven't been idle and I have been toodling around the internet looking for this stuff because politics is very much what I do. This has been a fun day for me. I found a couple links that might interest you, libcom.org and Libertarian Marxism. So first off they both admit that Libertarian was not just some other way of saying anarchist. The writers of the late 1800's and early 1900's don't mention it from what I can find. What has happened is that in the 1930's to 1950's a bunch of Socialists and Communists were looking back at the prominent anti-bolshevik and anti-beauracracy communists; and they wanted a way to refer to that side of Communism with one word. Because as libcom puts it, "We are also influenced by certain specific theoretical and practical traditions, such as anarchist-communism, anarcho-syndicalism, Autonomist Marxism, black liberation, council communism, feminism, ultra-left Marxism, and others." Which is quite a mouth full.

Where I think the confusion has happened is you think this happened a bit earlier than it did and right wing Libertarianism happened later than it did, but it also was forming in that time period. In the US, Libertarianism as it's popularly known was originally a reaction to the Great Depression and then the New Deal. So almost exactly the same time period, which explains why Rothbard would say they stole the word from their enemies. They were in direct competition for it. As for my stance on all Libertarians being ultra capitalists or useful idiots, I'll have to read more of what libcom wants before I can say they specifically fall into that hole. Right now it does seem they want practical answers, not some magic eraser that makes government regulations and laws disappear. But some of their root influences definitely fall into that problem, anarchy cannot defend itself from statists without forming a state itself.