There has to be something else causing the issue. If you're seeing different execution plans, it's because the mechanisms used to generate those plans have different inputs.
"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