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.