Put any deleted video URL into the text bar (make sure it has ?v= in it). It should give you thumbnails. If it loads 6 thumbnails, copy the maxres thumbnails. If it loads 3 thumbnails, copy the sd thumbnails. If it loads 0 thumbnails, then the img.youtube.com servers have not saved the thumbnails for the video.
The best way to find deleted video URLs is to scan a playlist with MW Metadata Bulk and looking for ones that say "Deleted video". Additionally you can press Show Unavailable to get video metadata from Filmot.
Back to the YouTube Thumbnail Downloader