I've also noticed sites like TheVerge do native advertising in a way that's very hard to tell until you actually see the article. And I don't think I've seen any "Sponsored" or similar tag anywhere close to the article, which I believe is in Google's policy.

Google itself seems to be doing this, too (not properly labeling ads), while telling everyone else not to do it and penalizing them.