Random performance of stored procedure across databases I have a stored procedure that is installed on 30 databases across 4 servers.  We encountered an issue last night where 3 of these stored procs are now taking over 8 minutes (one 18 minutes!) to execute while all of the others are under 1 second.  2 of the SP's are on databases under the same server, the other is on another server.  

I have looked at the following and seen no improvement or rational explanation why. 


sp_recompile
update statistics
review indexes fragmentation compared with successful databases but recreated anyways. 
change proc for param sniffing problem/solution
Reviewed execution plan for anything shocking (estimated rows was WAY off but came back to normal after #2 above
drop and recreated procs with no changes
watch temp db, as proc uses temp tables nothing jumped out


We have changed the proc to be more efficient and now its executing under 1 second, but I cannot let go as to what is causing the existing SP to be fast in  90% of the situations, but seriously slow in the others.  Especially across 2 servers.  

Due to the speed and consistency for months, I am baffled as to what might have caused this.
I have looked at database settings using sys.database comparing one to another. 
The only differences I see are 
                           Slow setting / Normal Database setting


recovery_model         1 /          3
recovery_model_desc    FULL/        SIMPLE
log_reuse_wait         2    /       0
log_reuse_wait_desc    LOG_BACKUP/  NOTHING


Could this have to the with the above settings? 

The proc (which I can provide if needed, along with execution plan) reads data from tables and inserts into a couple of temp tables and returns a dataset.  from existing tables it only performs selects.  The tables are no bigger then 250,000 rows.  Some databases where the proc is running quick are in excess of 800,000.   So the 3 in question actually have a small overall data set. 

Any ideas of what to check ?
What else can i do to figure this out?
Have you checked the CPU / Memory stats across servers where one SP is significantly different from another? (I assume your I/O are of the same performance more or less)? 

I would also check various wait statistics, using Paul Randal's query as good starting point

http://www.sqlskills.com/blogs/paul/wait-statistics-or-please-tell-me-where-it-hurts/