I agree. It sounds like parameter sniffing is leading to issues. I would suggest updating the statistics on the tables being referenced. In addition to the solutions for parameter sniffing, just getting better statistics frequently solves the issue.
"The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood"
- Theodore Roosevelt
Author of:
SQL Server Execution Plans
SQL Server Query Performance Tuning