Skipping taxes and using cash is only a problem if it's too widespread and the government really has genuine trouble collecting money even for the most basic needs of the society. Luckily, using cash to evade taxes is practically only possible for small entrepreneurs who can manage maintaining both the real income flow and the official income flow, and these people are also those who benefit from it the most.
It's the big businesses who practically need to log all sales and transactions by the book. Companies which have lots of employees and locations can't possibly maintain such double books in practice, not to mention keep it secret. (They can try smart "tax planning" via remote jurisdictions and tax havens though, which on the other hand isn't generally available for the local entrepreneurs.)
However, if you buy a lunch or pay your barber with cash, is it right that he gets your cash and the government gets nothing? Wrong. The minute the bistro owner or barber goes buy food from a chain store or fills up at the petrol station, VAT and other taxes will be paid and the money will re-enter the official circulation.
At best the money will bounce a few times between a few local entrepreneurs until it eventually becomes taxed again. How much effort is worth spending trying to chase these pennies?
What if efficient taxation reduces the amount of transactions? This happens all the time, and then both the tax man and the entrepreneurs lose.
What if all that unaccounted local cash flow actually lubricates the economy, making better and more efficient use of money, and thus generates larger total taxable flow of money?
The percentage of untaxed cash flow also serves as an indicator of how aligned people are with the government taxation level. If people are willing to make lengthy efforts to avoid taxes repeatedly, then maybe taxes are too high. If they only do it when it's convenient or for local shops, then maybe everything is close to fine.
It's not so black and white whether it's a "huge cost for society" as it's also "beneficial to society". The question is about trade-offs which need to be balanced, not overruled.