Because stored procedures are reusable ¾ not reentrant ¾ only one user can execute a given copy of a query plan at any one time. If two or more users try to execute the same procedure at the same time, SQL Server creates an additional query plan based on the parameters used on the latter execution. When the user finishes executing the procedure, the query plan is then available in the cache for reuse, for anyone else with execution permission on the procedure.
If a second query plan for a stored procedure is generated, there is no guarantee that it will be the same as the first one. For example, if a user passes a different set of parameters when the second plan is created, the query plans can be different. A new query plan for a procedure can also be different from a previous query plan if a user has updated statistics or added an index to a referenced table any time after the previous query plan was generated.
Updating statistics or adding an index does not force recompilation, but the newly compiled query plan can be different because it might take into account the different (or additional) information. The additional copies of the query plan stay in the procedure cache until they are swapped out, and can cause one execution to run very differently from another (although the returned results will be the same).