The logical conclusion is that they have permission, not that one of the largest companies in the world made a legal mistake that the "We Are Not A Lawyer"s on HN can see right through... for (at least) a second time. Keep an eye out for Oreo packages with Android branding material on them, in the style of: http://cdn.redmondpie.com/wp-content/uploads/2013/09/kitkata...
I do find myself curious what the negotiations look like when Google wants to not just use Oreos, but not slather all their material with "Oreos are a registered trademark of blah blah blah", which is pretty unusual.
Even with negotiations, If a engineer said in a Google youtube talk "Oreo is Americas favorite android," they could set themselves up for trademark infringement.
If Google had a line in a blog post that said, "It's better than real Oreos", they could likely be sued.
Oreo would not like Google saying either of these things. So Oreo needed to make up legal documents to map out all the things Google is allowed to say about Oreo Android. It seems like an unnecessary legal headache - one for dubious marketing gain.
Licensing a trademark means not having to worry about such fine-grained details. There's no reason anybody would have a problem with "Oreo is Americas favorite android" What is there to sue over? The damn thing is called "Oreo"
Same with your other example. That line is clearly humor, and keeps the cookie brand's name in people's minds.
It's the same with kit kat, they probably couldn't just use that, either.
But it's a win-win for both parties, I doubt either of them paid.