Stored procedure takes 18 seconds on first load, 0 seconds on subsequent loads, waiting several minutes makes it slow again
The issue was the setting "Auto close" was set to true on a series of databases on the server. Even though the databases were unrelated their "auto close" setting was flushing all execution plans on the server. 

Here are the types of log issues you will see with auto_close set to true: 

SQL Server has encountered 24 occurrence(s) of     cachestore flush for the 'Object Plans' cachestore (part of plan cache) due to some database maintenance or reconfigure operations.
SQL Server has encountered 24 occurrence(s) of cachestore flush for the 'SQL Plans' cachestore (part of plan cache) due to some database maintenance or reconfigure operations.
SQL Server has encountered 24 occurrence(s) of cachestore flush for the 'Bound Trees' cachestore (part of plan cache) due to some database maintenance or reconfigure operations.


As you can see in this article, NEVER SET AUTO CLOSE TO TRUE!!! http://sqlmag.com/blog/worst-practice-allowing-autoclose-sql-server-databases