ps. (11/16/2010)
In some cases, query processor may keep two plans, 1) without using parallelism, 2) using parallism and use either of them.
Nope. Recently debunked by Paul White (I'll leave it to him to come up with url, I'm working on a freshly installed machine)
If there are multiple plans (ie with different plan handles) then either set options are different or (user is different and query is not safe for reuse between different users)
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