If you're looking for the why, here's a possibility from Linchi Shea's Blog:
To create the best query plans when
  you are using a table on a linked
  server, the query processor must have
  data distribution statistics from the
  linked server. Users that have limited
  permissions on any columns of the
  table might not have sufficient
  permissions to obtain all the useful
  statistics, and might receive aless
  efficient query plan and experience
  poor performance. If the linked
  serveris an instance of SQL Server, to
  obtain all available statistics, the
  user must own the table or be a member
  of the sysadmin fixed server role, the
  db_ownerfixed database role, or the
  db_ddladmin fixed database role on the
  linkedserver.
(Because of Linchi's post, this clarification has been added to the latest BooksOnline SQL documentation).
In other words, if the linked server is set up with a user that has limited permissions, then SQL can't retrieve accurate statistics for the table and might choose a poor method for executing a query, including retrieving all rows.
Here's a related SO question about linked server query performance. Their conclusion was: use OpenQuery for best performance.
Update: some additional excellent posts about linked server performance from Linchi's blog.