If the first guy through creates a plan that uses a scan, unless something fires a recompile of the procedure or the plan ages out of cache, it's going to stay in place. You might want to take a look at the OPTIMIZE FOR query hint as a way to avoid this issue.
"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