Random performance of stored procedure across databases
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/