Contact was already underway - and other diseases mimicking the big S
Note that contact with North American natives was already common, as the rich fisheries around Newfoundland were already being exploited by Europeans well before Columbus set out - but under tight commercial secrecy.
Another illness produces bone changes very similar to Syphilis - this accounts for the not-actually-similar articles twenty years ago, as those skeletons at first seemed to prove that S had existed long before contact with the Americas - but it turned out to be another disease.
Syphilis was the most common cause of death in the U.S. as late as 1940 - but was rarely mentioned in the death certificate as listing the final symptoms spared family feelings.