The main powers I'm curious about are Rome (c. 2nd century) and the Umayyad Caliphate (7th-8th centuries), including the Andalusian Umayyads (8th-11th centuries)
For diverse reasons, (regarding Rome we had a recent thread about it there), it's unlikely.
Not that they didn't had a maritime technology (both material and immaterial) that allowed long-range trade (especially late Umayyads), but we're talking about mediterranean or coastal atlantic navigation that have a quite different settings than plain sea for at least a month.
At the very best, the XIIIth century could do it, assuming they adapt
out of nowhere mediterranean early carracks for atlantic navigation but that's all.
Regarding Vikings, as the OP specifically ask for sustained contacts between America and Europe, I must disagree once again : the contacts that existed historically (and that were more or less regular) were between Groenland and North America, never directly from Europe.
Not only for "economical" purposes (as Greenland needed commodities they couldn't find in their own region, and with Europe being too far for being a main provider), but for technological purposes : scandinavians ships while fit for long-range expedition, didn't really went too much in plain sea, preferring coastal or island jumping navigation.
If they didn't maintained IOTL regular contacts with even Greenland, it's not because they didn't tought about it, but because it wasn't neither interesting ("If they knew about America they" argument doesn't really hold : Greenlanders knew about America at least up to the XIV century, and nobody gave a shit) or easy to do.
Exactly. Thats why they called Labrador Markland.
Well, yes exactly why. The goal of their expedition was wood, and when they found some they called one of the land "Woodland". Calling everything they named too much litterraly wouldn't have looked good on sagas (And yes, fouding the land of wine looks better than land of wood : it's why we remember the former and not the latter).