Brent Ozar has a guide on troubleshooting parameter sniffing:
Parameter sniffing fixes are based on your career progression with databases, and they go like this:
1. Reboot the server! – Junior folks panic and freak out, and just restart the server. Sure enough, that erases all cached execution plans. As soon as the box comes back up, they run rpt_Sales for China because that’s the one that was having problems. Because it’s called first, it gets a great plan for big data – and the junior admin believes they’ve fixed the problem.
2. Restart the SQL Server instance – Eventually, as these folks’ careers progress, they realize they can’t go rebooting Windows all the time, so they try this instead. It has the same effect.
If a reboot can’t fix the problem, I’m out of ideas…
By the way, I second Brent’s recommendation of Erland’s query plan article. Erland doesn’t publish frequently, but when he does it’s worth the wait.