Can you post the procedure along with the two execution plans (as .sqlplan files)?
Gail Shaw Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci) SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability
We walk in the dark places no others will enter We stand on the bridge and no one may pass