Stuck Execution Plan?

Using SQL Server 2000 SP4.

There is a relatively complex stored procedure that usually completes in
less than 20 seconds. Occasionally it times out after 180 seconds. The SP
is called via ADO 2.8, using adCmdStoredProc command type. If I use
Profiler to capture the EXEC that ADO sends to run the procedure, and run
that from QA, the procedure completes in less than 20 seconds as it should.

The procedure is created WITH RECOMPILE. One additional twist is that
sp_setapprole is called from the client before running the procedure in
question. This may be irrelevant, because even if I include the same
sp_setapprole call when running the procedure from QA, it still executes
quickly, and even if I comment out the call to sp_setapprole in the client
code, the proc still times out when run from the client.

The only thing that fixes it, at least for a day or two, is DBCC
FREEPROCCACHE. So it appears that a bad plan is somehow stuck in memory and
is only used when the procedure is called from the client app, and is not
flushed even though the procedure was created WITH RECOMPILE.

Other than scheduling the DBCC call to run every night, is there anything
else I could try to get this resolved? Thanks.

--
(remove a 9 to reply by email)