We were seeing the same thing. Maybe 5% of our videos did not have the maxres thumbnail. However, so far 100% of our videos have the standard resolution thumbnail, which is high enough resolution for our purposes, so we switched to that. That URL is mentioned in the answer from @android-enthusiast :

http://img.youtube.com/vi/<insert-youtube-video-id-here>/sddefault.jpg