Hey, thanks for your detailed feedback, much appreciated!
I have another question for you — what if you create a whole new post with several images, but if you set one as featured (not the first one) before the first publishing? Does the problem persist?
There's one another solution for your problem, but you'll have to install another related posts plugin instead of this one you are currently using. Don't worry, it's ours and it's basically identical to the one you are already using, except that it has a 'Custom field' option for your thumbnails.
First, go to your create-new-post page or — even better — in one of your previous already-published-posts. On the right top corner you should see the 'Screen Options' button; click on it for the drop-down menu to open. After that, tick the box next to 'Custom Fields'.
Now you should be able to see a new box below the editor called 'Custom Fields'. Create new custom field, name your image that you would later like to use it as a thumbnail for this specific post (something like "Featured thumbnail"), enter the URL of the image you would like to use as a thumbnails and finish with the click on the button "Add Custom Field". Of course, don't forget to save this draft, or publish the post when you're ready.
After that, visit the settings of (y)our plugin and scroll down to the bottom. The option called "Use custom field for thumbnails" should now be available, tick the box next to it, and select the value you've set up before. Here's a screenshot for easier navigation: http://cl.ly/image/2K3t0L1L2Q1E
Now, the important thing is this: the value of the Custom Field stays the same for every new post, while the URL of the image (obviously) changes. In other words: the name of the Custom Field stays the same, images change. That's because once you set up your settings in the plugin settings (when you choose which value our the Custom Field our plugin should use for the thumbnails), you won't have to change it again in the future.
Once you have set this up, you just add a Custom Field with every new post, set the image you want to use for the thumbnail, while the name stays the same. Also worth noting is that you should keep the images you want to use for thumbnails as square as possible and that they're not too big. The perfect size would be anything bigger than 150x150 pixels, but that is not that crucial. Just don't use the biggest images you can find, because this can return you some problems.
Sorry for this long, too-long reply and please — do not hesitate to get back to me if anything was unclear or if you have any kind of additional questions. I'm also available for a video-call anytime you want, if you think you need my assistance! I'll be more than glad!
Looking forward to your reply! Take care!