A. Chances are this is due to the use of temporary tables in the SP :-
In SQL 7.0, a stored proc will be recompiled whenever a table is encountered that did not exist at the time the stored proc was created. So, if you scatter the creation and use of temp tables throughout a stored proc, the stored procedure will undergo multiple recompilations. However, if you place all your temporary table creates at the beginning before any other TSQL then there will only need to be one recompilation when the first temp table is referenced. Make sure you create the relevant indices on the temp tables at the start as well. The reason for this is to get better optimization for the later queries in the SP. With 6.5 and below, the optimizer didn't know what indices were available on the temp tables and so had to guess at the start of the sp. These guesses would often lead to inappropriate access plans.
You can also try putting the "OPTION KEEP PLAN" hint on selects to reduce the recompilations.
For more info on the above see http://msdn.microsoft.com/library/techart/sqlqa.htm
There is also a bug you may be running into (fixed in SP1). If the following conditions are true you may be getting excessive re-compilations :-
sp is in master
db being referenced is in 65 compatibility mode
concat_null_yield_null is being set (usually because you are using ODBC)
