Are You Still With Me So Far?
All these arctic Islands, Iceland, Svalbard, the Franz Josefs, Novaya, Severnya are host to large colonies of sea birds and migratory birds.
So during open water season, we'd see birds coming from and going to these islands.
Now, I don't know what the average ranges of these birds are. But I would assume that since they colonized all of these islands, that they can go quite a distance out and that you'd see them in open water.
After a while, you might start to notice them and notice that come evening, they all seemed to be heading in the same directions. You might start to wonder where they've been going. You might start to think that there might be land over that way.
Or maybe you just get interested and want to see where the birds are going, in hopes that it will lead you to humpbacks or bowheads or something.
And on occasion, given bad seas, bad weather, any number of freak events, you might figure that striking out after the birds might be the best way of surviving.
It wouldn't just be birds. Most of these archipelagos contain mountains that can get fairly high. Svalbard, Novaya Zemyla and Svernaya Zemyla all record high points of in excess of 5000 feet. Franz Josef's highest point is about 2500 feet.
That means you can see them from far off. How far? A person of average height can see about 3 kilometers at sea level. A person 12 meters up can see 13 kilometers. Visibility from the top of the Empire State building is about 130 kilometers How far off can you see an Island with a 5000 foot tall mountain?
The math is frankly beyond me, I'm lazy. If anyone's interested, here's a calculator:
http://mintaka.sdsu.edu/GF/explain/atmos_refr/altitudes.html
My completely uneducated guess is that within 100 to 200 kilometers, odds are that you might see it on the horizon.
It's also likely that on very clear arctic days, with low hanging clouds of ice crystals and good refraction, you could see reflections in the sky in the directions of islands. Such sky reflections were often seen by arctic explorers. I don't know if it lead to any discoveries, but the phenomenon was well documented.
So what this means is that seagoing Thule wouldn't necessarily have to be going right at the target. They might only need to come within a couple of hundred kilometers to realize that there's some kind of land out there, and have a decent idea of where to go.
So it's likely that at least the nearest Island groups - Svalbard and Iceland would be found by the Greenland East Coast Thule. Both Svalbard and Iceland are good whaling islands, and were known in OTL as sites from which whaling efforts took place.
The Thule whalers would be seeing these Islands during the summers, during their most hospitable phases. They might even be marooned there for spells, getting to know the lands, living off of birds, fish, sea mammals, etc. They'd certainly be in a position to assess the possibilities of the lands in terms of supporting herd animals or agricultural plants and microlivestock.
So, over time, there'd be enough accumulated knowledge and awareness of the locations and potential of Svalbard and Iceland that you might get winter or summer colonization efforts.
Summer colonization would be only by boat, obviously, and would involve at best some of the key crops and perhaps some microlivestock.
A winter expedition over the ice would allow dogs, musk ox, caribou and a wide range of supplies and artifacts, as well as more likelihood of women and children.
Why colonize at all? Displacement wars. The East coast of Greenland is full of competing lifestyles or subcultures, competing within themselves - Sheep herders vs Caribou herders vs Musk Ox herders, different agricultural groups, different hunter gatherers, different traders etc., and between groups.
For a group on the losing side, the prospect of retreat to a vast uninhabited Island might well be quite attractive.
Now, let's set Iceland aside for a second, and concentrate on the mechanics of expansion from Svalbard to the rest of the arctic.
Past Svalbard, I don't have much for whaling activity. Belugas are found around Franz Josef land, but I don't think its a site from which Bowheads are hunted. The range of Bowhead whales do include the waters around Franz Josef Land and the Eastern coastal regions of Novaya Zemyla. So its possible that Svalbard whale killing expeditions might be drawn out to the point at which seabirds might indicate the presence of lands further on.
In my view, its not likely that deep sea whaling would extend much further than Svalbard. The Svalbard Thule population would at best be a fraction of the Greenland East Coast population, and it wouldn't be hooked into the Ellesmere trading network. So whaling around Svalbard would probably be lower intensity, which means less likely to get drawn out further into deep sea.
But then again, there might be a couple of other factors encouraging discovery of Franz Josef.
First, there's that intervening island, which makes Franz Josef two jumps, one of 100 kilometers, the second of 200 kilometers. That's a couple of short jumps. At those ranges, you could probably guess at the existence of the intervening Island not too far beyond Svalbard's waters. And once you got there and were sailing around there, you could probably guess at a larger archipelago somewhat further on.
Why go there? Overpopulation or political or social stress on Svalbard. Useful area on Svalbard is only about 6,000 square miles. It might fill up fast. Even if Thule are able to maximize territory, literally grow or extend soil and make extensive use of sea resources.... there might be pressure to see what else is out there.
Once it is identified and explored during the summer (it would suck to try exploring in the winter - all you'd find would be ice, snow and darkness. Summer's the best time to look these places over), Franz Josef could seem very attractive for colonization. It would be a land potentially ripe for caribou, teeming with birds and sea mammals, even possessing some agricultural potential. It's likely that we'd see colonization of Franz Josef, sooner rather than later.
From there, we have the leaps from Franz Josef to Novaya and Severnaya Zemyla's. They won't be drawn by whaling, I don't think that there's a need for whaling given the local sea mammal populations, and the potential of the land.
Again, though, I'll note that Bowhead whales do range to the south as far as Novaya Zemyla's eastern coasts. The Franz Josef islands are very close to permanent polar ice, if they do hunt whales, they'll head south, which might lead them to Novaya Zemyla. Or at least, lead them to regions of seabirds heading that way.
Svernaya Zemyla would be the furthest. There are intervening islands. It's possible that little more than population pressure, dumb luck, and perhaps an emerging faith based on past lore that there are more lands and islands out there, might lead to explorers getting far enough out to follow seabirds back to it.
Severnaya Zemyla is ice locked most times. Not necessarily a fatal flaw denying access to the Thule. Expansion this time would probably be in part based on experience and lore of past colonizations.