Remote Query Cost - High Row Count
In versions of SQL Server earlier than 2012 (plus some patching), Linked Server permissions needed SA privs to use statistics information when processing remote queries. That could be what's messing you up.

For more information, see Conor Cunningham's talk on distributed queries here.