Remote Query is slow when using variables vs literal

I've searched everywhere for this situation and can't find a solution.

Here is the table I want to UPDATE on server 2:

(Stuff Id UNIQUEIDENTIFIER
, stuffname NVARCHAR(64))

I need to update it from server 1.

So I have been attempting this:

DECLARE @newstuff nvarchar(64)

SELECT @newstuff = 'new stuff'

UPDATE [server2].database2.dbo.Stuff
SET stuffname=@newstuff
WHERE stuffId='4893CD93-08B3-4981-851B-5DC972288290'

That takes 11 seconds. This next one using a literal runs in under 1 second

UPDATE [server2].database2.dbo.Stuff
SET stuffname='new stuff'
WHERE stuffId='4893CD93-08B3-4981-851B-5DC972288290'

I have compared the actual execution plans. The slow one is doing a Remote scan that takes 100% of the cost, plus 5 other steps (filter, table spool, compute scalar, remote update, update). The fast one just does the UPDATE and Remote Query steps. I need to use variables, so I need a way to force it to do the whole query remotely.

I have tried using OPTION(RECOMPILE) but server1 is using SQL Server 2005. server2 is using SQL Server 2012. I can't change the database structure at all on server2 without serious problems. I am not having any authentication problems. I have tried aliasing the table when updating it.

I have also tried using Openquery. When I put the id filter within the query string, it gets back down to under 1 second:

UPDATE OPENQUERY([server2], 'select stuffname, stuffid from database2.dbo.stufftable where contactid=''4CA1D489-9221-E511-A441-005056C00008''')
SET stuffname = @newstuff

But I need that id to be a variable as well, and that open query does not take variables (http://ift.tt/1NDHncD). I tried running Openquery with the id filter outside the query, but that runs in 4 seconds. It's better than 11, but not great:

UPDATE OPENQUERY([server2],'select stuffname, stuffid from database2.dbo.stufftable')
set stuffname=@newstuff
where contactid='4CA1D489-9221-E511-A441-005056C00008'

Of course, I run openquery using exec(@sql), but I really don't want to go that way. I could do the whole update statement that way using literals and not even use OPENQUERY and get the same sort of result anyway.

Is there any way for me to get this performance fixed without using exec(@sql)?