If you can post the execution plans, I would be guessing less, but, guessing, I'd say that it's probably a parameter sniffing issue. Take a look at the estimated values for each of the plans.
And yeah, I'm happy to see nice consistent behavior on query hints. They're frequently more painful than helpful.
"The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood"
- Theodore Roosevelt
Author of:
SQL Server Execution Plans
SQL Server Query Performance Tuning