Thanks to @vvaidya I managed to narrow down the possibilities and identified the issue. Tried #2 again and sent email to a pc with Outlook 2016 and it worked.
I suspect Outlook 2013 has a slightly different way of handling embedded images, the image does not show in the mail but was sent as an attachment instead.