Please correct me if I'm wrong, but wasn't one reason this thing is such a headache that, right now, there is no way for US companies to do this?

Because US companies are subject to the CLOUD act, they can be ordered to hand over user data to US agencies, whenever this data is under the company's control. It's irrelevant if the data center is located in Europe, the US or anywhere else, as long as the US company has control over it.

If Facebook could solve this issue by simply doing their behaviour targeting inside EU datacenters, I doubt they would write this down even as a risk, let alone as strange veiled threats.

That was just my understanding of the whole issue, which might be wrong though.