The plan files are indeed very similar. However, I disagree when you say that the query is something simple. I don't see the full query, but I see that there are umpteen calls to a scalar function which gives me an uncanny feeling.

Could you post the full text of the stored procedure, as well as the function?