Exist on table from linked Server giving Error 4104
The 4104 error occurs because you are using 5 part naming in your where clause. 

For example:

SELECT TOP 100 *
FROM [ServerA].[MyDB].[dbo].[Table1]
WHERE [ServerA].[MyDB].[dbo].[Table1].[foo]=5;


Will throw the error:

Msg 4104, Level 16, State 1, Line 17
The multi-part identifier "[ServerA].[MyDB].[dbo].[Table1].[foo]"  could not be bound.


Solution: using aliases

SELECT top 100 *
FROM [ServerA].[MyDB].[dbo].[Table1] AS T1
WHERE Exists( SELECT * FROM [ServerB].[TheirDB].[dbo].[TableA1] AS T2
              WHERE T1.[foo] = T2.[bar]);