Make it a legal requirement to mark paid promotions and anyone found to be doing paid promotions without marking it is at risk of huge fines.

I recall that in the UK, TV programs are already required to do this.