Definitely looks like parameter sniffing (or more correctly, the lack thereof)
http://sqlinthewild.co.za/index.php/2008/02/25/parameter-sniffing-pt-2/
Can you post execution plans please?
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability