I am curious to know in reference to this article
a>whether any dynamice sql statement were created within store procedure
b> is it possible to splitting it into multiple small stored procedures and calling them from a single stored procedure
c> are you generating any Errors from Stored Procedures(raise error) or try-catch in case sql serer 2005 to return to application
d> Does the enduser as that permission to call this store procedure & is the owner of this store procedure & how it is calling, is it calling with full qualify name
e> if store procedure is not called by qualifying the owner name, SQL Server enters the compile code and acquires a COMPILE lock on the procedure & determines that a new plan is not required assuming no other reasons apply, so it does NOT recompile the plan at this point due to the lack of qualification. However, the extra step of getting a COMPILE lock on the procedure can cause blocking contention in severe situations
f> are you using parameterization in your store prodecure for sql statement & which are executed using sp_executesql.
g> KEEP PLAN option is helpfull if you are creating any temp table, as no plan is generated untill they are created. Microsoft says that to ensure that the optimizer uses the best plan in all cases concerning temporary tables, a special algorithm was developed to be more aggressive with recompilations.The algorithm states that if a temporary table created with a stored procedure has changed more than six times, the procedure will be recompiled when the next statement references the temporary table. KEEP PLAN does not prevent recompilations altogether, it simply prevents those caused by more than six changes to temporary tables referenced in the procedure.
h> The following five SET options are set to ON by default:
If you execute the SET statement to set any of these options to OFF, the stored procedure will be recompiled every time it runs. The reason for this is that changing these options may affect the query result that triggered the recompilation. using the option of KEEP PLAN here won't help to avoid the recompilation because the cause of the recompilation is from the SET statement.
i> The following table lists some common SET statements and whether or not changing the SET statement in a stored procedure causes a recompile:
Set Statement Recompile
Set quoted_identifier No
Set arithabort Yes
Set ansi_null_dflt_on Yes
Set ansi_defaults Yes
Set ansi_warnings Yes
Set ansi_padding Yes
Set concat_null_yields_null Yes
Set numeric_roundabort No
Set nocount No
Set rowcount No
Set xact_abort No
Set implicit_transactions No
Set arithignore No
Set lock_timeout No
Set fmtonly No
The reason i focused on recompile is that as you menioned that your store procedure is using WITH RECOMPILE clause,while above specified steps is implictily recompling procedure cache which i thing is double overhead. as i hope the above information might have already been considered while troubleshooting store procedure. i just try to add some more additional tips if that helps.