It might also be worth checking your web logs as query string parameters can also be vulnerable to SQL injection.

Try a search for apostrophes or any SQL keywords.

Just a thought but

http://omnibuzz-sql.blogspot.com/2006/11/parameter-sniffing-stored-procedures.html

Worth a read as it sounds like you're encountering the same symptoms we had.

It explains what the effects of parameter sniffing can be.

That said...