Suddenly Slow Execution Plan for Stored Proc
This issue is called parameter sniffing.

Later versions of SQL Server give you more options in dealing with it such as OPTION (RECOMPILE) or OPTIMIZE FOR hints.

You might try declaring variables in the stored procedure, assigning the parameter values to the variables and using the variables in place of the parameters as it sounds as though most of the time you are getting a reasonably satisfactory plan.

Normally the most catastrophically bad plans are those compiled for parameters with very high selectivity but ran with parameters with low selectivity.

Assuming the plan generated is more robust with this approach and satisfactory for all parameter values then the advantage of this approach over that suggested by JNK is that it does not incur a compilation cost for every call. 

The disadvantage is that for some executions run time might be greater than for a plan tailored specifically for those parameter values so it is a trade off of compile time vs execution time.