Anarcho capitalism, which is not necessarily the view of every libertarian (some being "minarchists"), would be the absence of any government authority. Without a government the regulation you speak of is non-existent. There is no contradiction.
More foam-at-the-mouth anarchists tend to be empty vessels - louder, so they attract the disenchanted.