OK, solved it!
I did some cleaning up with 'efibootmgr' as UEFI was getting cluttered but I doubt that was the issue.
What I did do was go into the BIOS and set USB-HDD as the first boot device. Before that I simply choose the wanted boot device using F12, apparently that mucked up the boot sequence on this particular machine/mobo.. 
