@jhaine : Ok, a little update. I've read up a bit and I get your idea about AIS now, it was actually a more plausible than I first thought. However, it's still limited to just position and a few basic ship data, I can't transfer custom Arduino sensor data (battery monitoring, burglar alarm, etc).
So, NB-IoT or LTE-M it is. But it seems that the range difference isn't as big as I first was told. Here's one excellent article that got me leaning back towards LTE-M , seeing the small differences in coverage/range and power consumption, with LTE-M even outperforming NB-IoT in certain conditions (check the conclusion part for a quick summary). This made me very happy, since it will probably save me a bit a of trouble. Unless you, or anyone else here have got any other input that I should consider, I think I'll aim for LTE-M.