Hi it's no big problem for youtube as they store the picture with the video id in the url, others suck ...
for my quick use i didn't find plugin doing it completely, so i use Viper's Video Quicktags, which grabs the image and puts it instead when JS is disabled, so i just load the_content as it goes and trim the things off to get the address. The way is a bit jerky but it works for now. Hope helps.
<?php if (have_posts()) : ?>
<?php while (have_posts()) : the_post(); ?>
$nolines = '/[\n\r]/';
$cont = get_the_content(null, 0, '');
$cont = apply_filters('the_content', $cont);
$tillnolines = preg_replace($nolines, ' ', $cont);
$till = preg_replace('/^(.*)(com\/watch)/', '', $tillnolines);
$almost = preg_replace('/(alt\=\"YouTube Preview Image\")(.*)/', '', $till);
$core = preg_replace('/(.*)( src=)/', '', $almost);
echo '<img class="prev video" src='.$core.' alt="" />';
<?php endwhile; endif; ?>