With the understanding that QR codes can contain any type of data, I'm just covering URLs here, since that seems to be what most advertising uses them for.
The best QR codes:
work in the context of the advertisement
a poster for a movie should link to something that helps promote the movie. A website is kind of boring, but a trailer isn't.
the best one had a short URL which redirected to a YouTube URL, which, in the iPhone, redirects to the YouTube app. That allows the studio/promoter to track where/when the URL was accessed, and shows off a movie in the way most people want it showed off, i.e. in video. For the record, it was The Mechanic, scanned in a Canada Line transit station, using a qrs.ly URL that redirects (presumably tracking before sending off to YouTube).
use the same colour scheme of the advertisement. The example at http://www.flickr.com/photos/boris/5504410554/ is not horrible.
use a tracking URL, ideally one URL per advertisement, so that the promoter can know exactly which QR code was scanned. Once the link is shared, then it becomes hard to track that it came directly from a QR code
doesn't link directly to the Facebook page. Ultra-boring.
doesn't re-use URLs. I'm looking at you, Air Canada.
isn't curved around a pole. A campaign in Vancouver postered those poles typically used for concert announcements, but the app I used (or the iPhone camera) couldn't pick it up. Multiple locations, and after 10 seconds of trying on each.
make me feel cool for scanning it. A campaign for a Canadian university included a small QR code in their bus advertisement (inside the bus, above heads of riders), making me have to get up and get close to the ad. On a moving vehicle, even the most graceful individual would look awkward doing it
rewards me with a coupon, or makes me smile.
Problems QR codes have (some of it rewording the above):
pretty nerdy, in that it doesn't feel cool to walk up to an ad, load up the app that scans them, wait for the app to scan it properly, then consume whatever it's linking/showing/etc.
not obvious which app you should use. People have to ask their friends which one they use.