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...