SQL Server – Query Running Differently on SQL 2005 vs SQL 2008 R2

At my office, we have a query that is pretty ugly, but runs pretty well in production and in the development environment (20sec, and 4sec respectively). However in our testing environment it takes over 4hrs. SQL2005(+latest patches) is running in production and development. SQL2008R2 is running in testing.

I took a look at the Query Plan, and it shows that SQL2008R2 is using TempDB, by way of a Table Spool (lazy spool) to store the returned rows from the linked-server. The next step is showing Nested Loops (left anti semi join) as eating up 96.3% of the query. The line between the two operators is at 5,398MB!

The query plan for the SQL 2005 shows no use of tempdb and no use of a Left Anti Semi Join.

Below is the sanitized code and the execution plans the 2005 plan in on top, the 2008R2 on bottom.

What is causing the drastic slow down and change? I was expecting to see a different execution plan, so that doesn't bother me. The dramatic slow down in query time is what troubles me.

Do I have to look at the underlying hardware, since the 2008R2 version is using tempdb I have to take a look at how to optimize usage of that?

Is there a better way to write the query?

Thanks for the help.

    INSERT INTO Table1_GroupLock (iGroupID, dLockedDate)
SELECT 
 Table1.iGroupID,
 GETDATE()
FROM Table1
WHERE 
 NOT EXISTS (
  SELECT 1
  FROM LinkedServer.Database.Table2 Alias2
  WHERE 
   (
    Alias2.FirstName + Alias2.LastName = dbo.fnRemoveNonLetter(Table1.FullName)
    AND NOT dbo.fnRemoveNonLetter(Table1.FullName) IS NULL
    AND NOT Alias2.FirstName IS NULL 
    AND NOT Alias2.LastName  IS NULL
   ) OR (
    Alias2.FamilyName = dbo.fnRemoveNonLetter(Table1.FamilyName)
    AND Alias2.Child1Name = dbo.fnRemoveNonLetter(Table1.Child1Name)
    AND NOT dbo.fnRemoveNonLetter(Table1.FamilyName) IS NULL
    AND NOT dbo.fnRemoveNonLetter(Table1.Child1Name) IS NULL
    AND NOT Alias2.Familyname IS NULL
    AND NOT Alias2.Child1Name IS NULL
   ) OR (
    Alias2.StepFamilyName = dbo.fnRemoveNonLetter(Table1.StepFamilyName)
    AND Alias2.StepFamilyNameChild1 = dbo.fnRemoveNonLetter(Table1.StepFamilyNameChild2)
    AND NOT Alias2.StepFamilyName IS NULL
    AND NOT Alias2.StepFamilyNameChild1 IS NULL
    AND NOT dbo.fnRemoveNonLetter(Table1.StepFamilyName) IS NULL
    AND NOT dbo.fnRemoveNonLetter(Table1.StepFamilyNameChild2) IS NULL
   )  
 ) AND NOT EXISTS (
  SELECT 1
  FROM Table3
  INNER JOIN Table4
   ON Table4.FirstNameType = Table3.FirstNameType 
  INNER JOIN table5
   ON table5.LastNameType = Table3.LastNameType 
  WHERE 
   Table3.iGroupID = Table1.iGroupID
   AND Table3.bIsClosed = 0
   AND Table4.sNameTypeConstant = 'new_lastname'
   AND table5.sFirstNameConstant = 'new_firstname'
 )

:: EDIT ::
Executed the query from a different SQL2005 instance, pretty much the same execution plan as the "good one". Still not sure how the two 2005 versions are running better to the 2008R2 linked server, than the 2008R2 instances to the 2008R2 instances.

While I don't deny that the code could use some work, if it was the code being the problem, wouldn't I see the same'ish exec plans across all of my trials? Regardless of SQL version?

:: EDIT ::
I have applied SP1 and CU3 to both of the 2008R2 instances, still no dice.
I have specifically set the collocation in the linked server, no dice.
I have specifically set permissions of my user acct to be sysadmin on both instances, no dice.
I have also remembered my sql server 2008 internals and troubleshooting, we'll see if I can track this down some how.

Thanks everyone for the help and the tips.

:: EDIT ::
I have done various permission changes to the linked server. I've used SQL logins, domain logins, I have impersonated users, I have used the "be made using this security context" option. I have created users on both sides of the linked server that have sysadmin rights on the server. I am out of ideas.

I would still like to know why SQL2005 is executing the query so dramatically different from SQL2008R2. If it was the query that was bad, I would be seeing the 4+hrs run time on both SQL2005 and SQL2008R2.