I generally prefer the oEmbed approach. It's mentioned on the SO question linked in Paul Irish's write-up. I'll throw together a sample at some point.

So playing around with the goal of "highest quality thumbnail" in mind, I notice that the oEmbed data appears to always return the hqdefault.jpg url, regardless of what's available.