stored procedure times out while subsequent runs take 1/6 the time
Sounds like stats are out of state, and SQL is going a full scan and loading all the data into buffer pool on the first run, then accessing that data from buffer pool for the rest of the runs.

Try flushing the buffer pool between runs and see if the times increase to confirm this.

Also can you post the execution plans?