DELETE from Linked Server table using OPENQUERY and dynamic criteria
In my experience, DML statements over Linked Servers is sllooowww (I believe that is the proper, technical spelling of this particular type of slowness ;-).

I found that the following setup was mucho faster:


Create a stored procedure on the remote server:


Call it something like RemoteTable_DeleteByEntryIDList
It should accept an NVARCHAR(MAX) parameter called @EntryIDs
The format of the data for that parameter will be a list of EntryIDs in XML
The parameter cannot be of type XML as that is not valid for passing over a Linked Server
The proc will do something along the lines of:

CREATE TABLE #TempIDs ([EntryID] INT NOT NULL);

;WITH cte AS
(
    SELECT CONVERT(XML, @EntryIDs) AS [Data]
)
INSERT INTO #TempIDs ([EntryID])
  SELECT tmp.[EntryID]
  FROM   cte
  CROSS APPLY (SELECT tab.col.value('./EntryID[1]', 'INT') AS [EntryID]
               FROM   cte.[Data].nodes('/row') tab(col)
              ) tmp;

-- optional: test to see if it helps or hurts
-- ALTER TABLE #TempIDs
--   ADD CONSTRAINT [PK_#TempIDs]
--   PRIMARY KEY CLUSTERED (EntryID ASC)
--   WITH FILLFACTOR = 100;

DELETE rt
FROM   RemoteTable rt
INNER JOIN #TempIDs tmp
        ON tmp.[EntryID] = rt.[EntryID];


Update your local stored proc to do something like:

DECLARE @IDsToDelete NVARCHAR(MAX);

SET @IDsToDelete = (
  SELECT EntryID
  FROM   dbo.LocalTable
  FOR XML RAW
);

EXEC [MyLinkedServer].[DatbaseName].[SchemaName].[RemoteTable_DeleteByEntryIDList]
     @EntryIDs = @IDsToDelete;