SQL Server - Linked Server error - Could not connect to server XYZ because Server being used: SQL Server 2012 SP3 
I just received a strange error (strange because it worked earlier) 

could not connect to server LNK_SRV because sa is not defined as a remote login



Not sure why we are receiving the error.

The sys.servers says is_linked = 0 for LNK_SRV - not sure why.
The following returns results 

select top 10 * from LNK_SRV.DBName.dbo.TblName


But the procedures are failing

exec LNK_SRV.DBName.dbo.ProcName


It was working fine before we dropped the linked server and re-added it.
Also, the LNK_SRV is being used as for replication as well.

Note: I am aware sa is bad. It will be taken care soon.
The linked server was also used for replication. 
The order of Subscribe and Create linked server was the issue. 

Reproduce the error:
1.  Drop the subscription 
2.  Drop the linked server
3.  Configure the Subscription first
4.  Linked Server next 
5.  Testing 
- a.    Select will return results
- b.    Exec proc result in error



Fix:
1.  Drop the subscription
2.  Drop the Linked Server
3.  Create the Linked Server first
4.  Configure the Subscription next
5.  Testing
- a.    Select will return results
- b.    Exec proc will succeed

Also, executing the following on Linked Server worked as well.

--Run this statement on LNK_SRVR
exec sp_AddRemoteLogin 'CurrServer','sa'