I recently had a rather odd problem which I have been unable to solve to my satisfaction so far.
The problem involves stored procedures which are compiled and cached. When calling the sproc from a c#.net 2.0 web application the call would timeout; however I could capture the call in SQL Profiler, run it in Management Studio and it would run great in sub second times.
The only solution I have found so far is to re-compile the sproc manually.
You could also try adding WITH RECOMPILE to the sproc and deal with the performance loss. This was suggested in a sqlteam thread:
A similar suggestion is on SQLServerCentral.com
After reading Ken Henderson's WebLog I am guessing that the cached plan is somehow getting corrupted and that running the code manually in Management Studio somehow uses a different cached plan. Perhaps plans are different for each user? Hopefully I can find and post a better solution.