If you can, post the actual execution plans of the query when it runs in 1 minute and when it runs in 10 minutes. 

That could provide some clues about what's happening.

Cheers!