I would try creating a stored procedure on the linked server to do the delete and then just call the one stored procedure from the other server. I have seen this improve performance. Something to try...