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:

ANSI_DEFAULTS

ANSI_NULLS

ANSI_PADDING

ANSI_WARNINGS

CONCAT_NULL_YIELDS_NULL

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.

Thanks

Jay