It's probably got nothing whatsoever to do with the cached execution plan. The optimiser is not allowed (in most cases) to spend minutes optimising a query.
What's probably causing the slow-down is having to re-load the data required for the procedure into the data cache. I'd guess that something like index rebuilds, checkDB or large data loads are done at night, hence displacing the data cache.
The solution here is to tune the query, it's probably requiring more data than it should due to inefficient queries or poor indexing and you mainly see the effects of that when the data has to be pulled from disk.
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)SQL In The Wild
: Discussions on DB performance with occasional diversions into recoverability
We walk in the dark places no others will enter
We stand on the bridge and no one may pass