Well, there's Tiger & Bunny which plastered product placement to the extreme of its real-life sponsors:
Each of the city's most famous superheroes work for a sponsor company and their uniforms also contain advertising for real-life companies.
The show features "sponsored" super heroes who fight crime, with their sponsors plastered all over them like NASCAR, and in some cases, even doing in-show commercials for the actual product (e.g. Pepsi). Some of these in-show sponsors were actually sponsors of the show. The old Tiger & Bunny website (it's since been changed) listed all of their sponsors which had product placement: via archive.org.
I don't know if these companies actually went to the producers to pay for advertising spots within the show. It's probably more likely that it was a two-way street, working much like how anime get made in general, where the producers/studio will look for sponsors with an idea, and a contract and agreement is made. So these companies went into it knowing how their product would be placed in the show.
When the show was adapted into a manga, all of the product placement was removed (for obvious reasons).