SQL Server : Job not reconnecting to restarted Linked Server
Querying the linked server seems to get it to reconnect. Calling sp_testlinkedserver doesn't always work, but a select statement will.

Sometimes there is a two minute lag from the start of the downed server to the next successful run of the job. In any case, it's simply a matter of waiting.