I wouldn't count the Iceland site as New World, myself. It's definitely part of the European history.
Greenland, (the west coast) on the other hand, was settled for about a thousand years before Columbus. There are tithe records in the Vatican showing payment of tithes in lumber and firs. During one of the Crusades a noble (royal?) night was captured, and the demand for ransoming him included, among other things, a Greenland falcon. There was regular trade with Norway or Sweden or Denmark--forget which--but during the plague years there were fewer and fewer ships, perhaps thirty years between voyages. Eventually one of the ships returned to Europe with the report that the population had vanished in the past fifty or so years. One of the unsolved mysteries of the Arctic.