Randomly Login Timeout Expired errors using OpenDatasource from SQL Server 2000

I have some JOBs running on SQL Server 2000, which are calling stored procedures or queries against remote SQL Servers (different editions).

The remote connections are done by using OPENDATASOURCE directly on the JOB... Other times the JOB calls a DTS, and is the DTS who does the remote connection and executes the Stored Procedure or gets a query results from the remote server. This would be an example of calling a remote SP directly from the JOB:

EXEC OPENDATASOURCE('SQLOLEDB','Data Source=REMOTESERVER;user id=user;password=pswd').MyDatabase.dbo.MyStoredProcedure 'Parameter1'

This has been working without errors. I don't know why during the last month, I'm having randomly errors on these kind of jobs... I've read some other posts and seems to be related to a security issue, but I repeat, the most of times the jobs are working, only some runs are failing with these errors.

ERROR 1 (When the job calls the remote SP using OPENDATASOURCE)

Executed as user: SERVER\user. OLE DB provider 'SQLOLEDB' reported an error.
[SQLSTATE 42000] (Error 7399)   [SQLSTATE 01000] (Error 7312)
OLE DB error trace [OLE/DB Provider 'SQLOLEDB' IDBInitialize::Initialize
returned 0x80004005:   ]. [SQLSTATE 01000] (Error 7300).  The step failed.

ERROR 2 (When the job calls a DTS, and the DTS calls an SP on other Server or gets a query result from a remote server, or do an update on a remote server)

Executed as user: SERVER\user. DTSRun:  Loading...   DTSRun:  Executing...  
DTSRun OnStart:  DTSStep_DTSDynamicPropertiesTask_2   DTSRun OnError:
DTSStep_DTSDynamicPropertiesTask_2, Error = -2147467259 (80004005)
Error string:  Login timeout expired      Error source:  Microsoft OLE DB
Provider for SQL Server      Help file:        Help context:  0
Error Detail Records:      Error:  -2147467259 (80004005); Provider Error:  0 (0)
Error string:  Login timeout expired      Error source:  Microsoft OLE DB Provider for SQL Server
Help file:        Help context:  0      DTSRun OnFinish:
DTSStep_DTSDynamicPropertiesTask_2   DTSRun:  Package execution complete.
Process Exit Code 1.  The step failed.

I really don't know what to check. After reboot the server the problems are still there. Any help from you guys would be appreciated.

EDIT 2019-02-14 16:15 -------------------------------------------------------------------------------------------

One of the solutions I found has been to change the Remote Login Timeout property from the default 20 seconds to 30 seconds, or to 0 (Zero means without timeout), by executing the next code:

sp_configure 'remote login timeout', 30  --Or 0 seconds for infinite
go 
reconfigure with override 
go 

From: https://support.microsoft.com/es-es/help/314530/error-message-when-you-execute-a-linked-server-query-in-sql-server-tim

I've tried this solution changing it to 30 seconds, but with the same result. Of course I didn't set it to 0 for obvious reasons, the timeouts are there for something. And also tried 300 seconds (5 minutes to make a login!) and still the same.

EDIT 2019-02-15 13:30 -------------------------------------------------------------------------------------------

Here again. I could do some more testing, and have new info regarding the issue. The errors I talked about are the errors that you can get from the Job History... But when I execute the call to the SP from the Management Studio the error message is different. The same call:

EXEC OPENDATASOURCE('SQLOLEDB','Data Source=REMOTESERVER;user id=user;password=pswd').MyDatabase.dbo.MyStoredProcedure 'Parameter1'

Launched from different SQL Server Instances and Editions works good. Launched from the original SQL 2000 Instance or other SQL 2000 Instances, I get this error message:

Could not execute procedure 'MyStoredProcedure' on remote server 'SQLOLEDB'.

So, the problem seems to be the calls using OPENDATASOURCE from SQL 2000 Instances... It's trying to connect to a server called SQLOLEDB?? What can be happening? The same call to the SP has been working well during long time. Why now is failing and giving this kind of error message?

Also tried to change the driver from SQLOLEDB to SQLOLEDB.1 , but got the same result.