While not huge, 53 million rows isn't exactly a small table. While it certainly could be parameter sniffing, it could also be that the data was driven out of memory by other requests and needed to be reloaded. That's probably why it took 10 minutes to run the first time and just seconds to run the second (for example).
--Jeff Moden
Change is inevitable... Change for the better is not.