YouTube thumbnail link doesn't work in all cases

As I understand it, YouTube only generates high-res stills for high-res videos. The first one you link was uploaded at a resolution of at least 1080p, while the second was less than 720p.

Looks like the only thing you can do is pull the video feed, check that to see if a high-res still has been generated and up-scale the smaller one yourself if not.

All¹ YouTube stills are presented in the 4:3 aspect ratio, so will always have black bars at the top and bottom if the video is 16:9. In HTML/CSS, this is easily combated by setting the image as the background of a div and sizing the div to the correct aspect.

¹ Except the mqdefault.jpg stills, which are all in 16:9 aspect (320x180)

Update 2015 : None of your 'maxresdefault' link seems to be working

Try these:

http://img.youtube.com/vi/<insert-youtube-video-id-here>/0.jpg
http://img.youtube.com/vi/<insert-youtube-video-id-here>/1.jpg
http://img.youtube.com/vi/<insert-youtube-video-id-here>/2.jpg
http://img.youtube.com/vi/<insert-youtube-video-id-here>/3.jpg