The algorithm used to pick the image is pretty straightforward:
1. If the post has a thumbnail, it uses that
2. If there's no thumbnail, it pulls the image attachment with the lowest menu_order.
In looking into this, it looks like the original source of the attachment-handling code dates back to 2008 and might not be applicable now that we have much better media handing. In fact, the posts you aren't seeing thumbnails for probably get all their images from the Media Library, not the old-fashioned attachment mechanism.
I've never seen this because I use post thumbnails on my blog. But I'm surprised it hasn't come up sooner.
I was wondering what the big feature would be in the next version. Guess I know now :)