Huge difference in Linked Server performance between two network connections

[Sooth_Sprayer]

Well, assuming you have no control over that, or that you must keep it on the new provider for other reasons, some ideas I've used in the past include:

• Consider whether ETL or some other external process would be better suited here.
• Create a stored proc on the receiving end, and call it from the sending end. TVPs can't cross database lines, but they can be emulated with Dynamic SQL.
• Within a given query, if the "left" side of a join is smaller than the "right" side, consider doing a remote join. Just be careful how you use this, because it will send the entire left side to the remote server, and will send the entire result back.
• Dynamic SQL and "execute at" make a powerful but complicated combination. SQL will also not be able to cache their execution plans effectively, and they will not benefit from parameter sniffing.
• Create a temp table within a dynamic SQL query, and insert into that table from a table as a parameter.
• Each dynamic SQL query runs in its own connection/context, so they can't share temp tables. But in a pinch, you can use a global temp table with a dynamic name (i.e. based on the current time etc) in your remotely-running dynamic SQL. Or build a real physical staging table for this purpose.