Timeout fixed by recompile

We have a very large app. 200+gig db with 3 databases and hundreds of
stored procs in each one. Its sql server 2000 (sp3) and asp.net 1.1. We
have a full DBA staff and troubleshoot normal blocking issues and other
valid timeout causes almost daily. We have seen an issue lately with
one of our stored procs where it decides it will no longer complete
when called from the web. It will timeout every time when run the web
front end until the proc is recompiled. While it is timing out, you can
run it from q-analyzer and it runs in <1 second. This sp is a single
select statement with 3 left joined tables, each one from a different
db on the same server. I am seeing others here who are experience
something similar but it seems no one has any ideas other than the
normal steps you take to troubleshoot a real timeout i.e blocking. I
took the code that makes the sp call and made a new project. I made a
button that calls on that problem stored procedure 10,000 times. When
the prod site is timing out non stop, I run my app and it runs the same
sp that times-out off the same database 10,000 times in about 4
seconds. Of course it also still works fine when run through analyzer.
We have thousands of users and this proc is run constantly. It normally
takes a week or so before the problem reappears. Recently it started to
come back every 15 minutes so the manual recompile wasn't enough. We
changed the proc to use dynamic sql and then executed it with
sp_executesql so it would use the same execution plan. Been working
fine for days now but I consider this a work around and it'd be great
to know what the real problem is. It's like .net is caching the
execution plan locally and then losing it for some reason after a time
and then is unable to get it back with the current connection. I guess
I should add that we have a data tier that all our sp calls are made
through so this proc is called exactly the same as the others in terms
of ado.net settings.