We had the same problem and I used a table-valued function to limit the data being transferred. In this way, the join was on the function and with a smaller results set being transferred over the network. The speed increase was huge in my case.

Ex. (from my bad memory)

Select ...

From vwLocalTable l

Inner Join fnGetRemoteData(l.filterVal) r

on l.key = r.key

where l.filtercol = "something"

We put this whole thing in a view to help to abstract the hole problem with linked server specs in sql.

Hope this helps.