One technique I have seen used successfully is to roll the query into a view at the remote site, allowing you to optimize the query at the remote site as much as needed. Then you simply query the view over the link.

In some cases this may not be possible such as if the queries are generated ad hoc, but this doesn't seem to be the case here since you can hint the queries.

Mike