Assuming your happy to accept a solution involving one of the plugins you listed under the “Partly woking:” heading.
Widgets of Posts by Same Categories
http://svn.wp-plugins.org/widgets-of-posts-by-same-categories/trunk/widgets-of-posts-by-same-categories.php
Only need literally 1 or 2 lines of code, depending on how you want to handle the “post does not have a thumbnail” scenario.
Around this area of the plugin file..
<?php
$postslist = get_posts("category=$cat_ID&numberposts=$numberposts&orderby=$orderby&order=$order&exclude=$exclude_posts");
foreach ( $postslist as $post ) :
?>
<li><a href="https://wordpress.stackexchange.com/questions/36643/<?php print get_permalink($post->ID); ?>" title="<?php print get_the_title($post->ID); ?>"><?php print get_the_title($post->ID); ?></a></li>
<?php endforeach; ?>
All you need to add there is something along the lines of the example on the has_post_thumbnail codex page.
if( has_post_thumbnail() )
the_post_thumbnail();
For example..
<?php
$postslist = get_posts("category=$cat_ID&numberposts=$numberposts&orderby=$orderby&order=$order&exclude=$exclude_posts");
foreach ( $postslist as $post ) :
?>
<li>
<?php
if( has_post_thumbnail() )
the_post_thumbnail();
?>
<a href="https://wordpress.stackexchange.com/questions/36643/<?php print get_permalink($post->ID); ?>" title="<?php print get_the_title($post->ID); ?>"><?php print get_the_title($post->ID); ?></a></li>
<?php endforeach; ?>
Though i guess it depends how exactly you want the implementation to work..
Does that help? 🙂