What if Facebook spend 2B USD on a product that was supposed to be wildly successful, but it failed big time, does that count as "costing the US tax money" as they never made the profit they could have made?
No, the companies are being hampered by not following local (EU) regulation, so they get fined because of it. Has nothing to do with where the company is from, it might as well have been Indian, Chinese or from South Africa, it has to follow the regulation in the places it does business.
I'm not familiar with U.S tax law but in the UK fines are not tax deductable. Not sure whether it matters that the fine was imposed by a foreign country.
For something to be tax deductible means that it reduces taxable income. Essentially it works like this:
Revenue - tax deductable business expenses = taxable income.