[mikeash]

You can charge for externalities without distributing them to the victims on a personal level.

You're right that precisely compensating a lung cancer victim is pretty much unworkable. But the statistics in aggregate are pretty clear, so you can collect that money as a tax without paying out precise compensation to each individual victim. This still produces the appropriate incentive to burn coal only when it's worth the full cost.

Your examples illustrate this principle. Your garbage collector probably has to pay a license fee, and has to obey noise regulations. UPS pays vast amounts of money for parking tickets. These could probably be calibrated better, but we don't just let these companies generate negative externalities at will.