UPDATE not working properly with linked server
The fundamental issue is: Which server processes the query?

When using a linked server query, the query is executed on the LOCAL server and uses the linked server to access data on the remote server. (Linked servers are subject to several limitations, some caused by running through the Distributed Transaction Coordinator (DTC).)

When using OPENQUERY, the query is sent to the REMOTE server and is executed there in order to return data to the local server.  (You will notice that in OPENQUERY the query uses a three-part name, since it all runs on the remote server, rather than the four-part name used for the linked server.)

A simple exposure to the limitations can be found in this thread: http://www.sqlservercentral.com/Forums/Topic948316-338-1.aspx

It mentions network topology, data types, type of remote server, the code in the query, etc.

EDIT: See more on the Guidelines for Using Distributed Queries at:
http://technet.microsoft.com/en-us/library/ms175129(v=sql.105).aspx

The subheading Other Guidelines mentions:  "To create the best query plans ..., the query processor must have data distribution statistics from the linked server. ... If the linked server is 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_owner fixed database role, or the db_ddladmin fixed database role on the linked server."

If your connection to the remote server does not have access to those statistics that might cause a poor plan.  Ideally not an inaccurate plan, but the query processor is imperfect.