A quick jaunt back to Rome, the Eternal Analogy.
Roman taxation was done in a way calculated to minimize collection headaches for the state. From the Republican period through to Diocletian at the end of the third century (and from there to the end of the Empire, with some modifications), Rome didn't collect taxes directly from her subjects. She took bids from tax farmers for the rights to collect from specific regions, collected from the winner, and considered that year's taxes paid. The contractor then set out collecting cash from the lucky province to recoup his investment and make a profit; anything he collected beyond his bid was his to keep. This worked out exactly the way you'd expect. It's why the authors of the New Testament show that Jesus turned no one away by emphasizing that he associated with foreigners, gentiles, lepers, criminals, prostitutes, and even tax collectors.
Even the most hardcore libertarians, not being anarchists, accept the need for some amount of government, and therefore for some amount of taxation. However free-market obsessed they may be, I doubt many would advocate outsourcing taxation to private companies.
Some other parts of the political spectrum, though...