One of the things that causes a recompile is when a significant change in the statistics occurs - like from updates. What I would do if you haven't already is run a profiler trace with one of the events being SP:Recompile. That way you can confirm that the procedure is being recompiled one or more times during execution. If that is the case you can use a query hint to suppress the recompiles. From books online (query hints):
quote: KEEPFIXED PLAN
Forces the query optimizer not to recompile a query due to changes in statistics. Specifying KEEPFIXED PLAN makes sure that a query will be recompiled only if the schema of the underlying tables is changed or if sp_recompile is executed against those tables.
EDIT: of course this are obvious repercussions with this - maybe the optimizer should change plans based on the latest statistics.
It is sounding more like the data is cached for subsequent runs. Why did you believe that the time is taken for execution plan compilation? If you run the trace I suggested you will know how the time is divided between recompiles vs. statement duration.