Ice Titan and Martin have some great ideas. Let me throw one more out there.
If your players are still dead set on traveling across the ocean, through territory that has never been explored with untold dangers, have one of the seven Linnorn Kingdoms suddenly, and unexpectedly, blockade Kalsgard. They aren't, after all, united and they're VIKINGS. Devise a story for why Kalsgard and one of the other Kingdoms would be at each other's throats. Design in such a way that it would take months for the situation to resolve.
Here's an example from my game. My players decided that they didn't want to waste their time trying to find Ulf. They went to the two named merchant guilds that travel across the Crown of the World - the Rimerunner's Guild and one other one named in the back of the book. The latter told them that they only deal with referenced clients, and both of them told the players that it would be 3-4 months before trade started up again. My players absolutely did NOT want to wait 3-4 months. I didn't make it off limits, but rather made the option less attractive.
If you go with the blockade route, you might run into the problem of your players railroading from the AP and wanting to get involved in the national turmoil. You'll have to take that into consideration and devise something that will make it less likely they'll want to do that.