Thanks Gianluca

The reason I was veering away from parameter sniffing is that this problem occurs even when the procedure cache is clear. I had considered the OPTIMIZE FOR query hint, but ideally I would like it to be OPTIMIZE FOR UNKNOWN which, unfortunately only appears in SQL 2008 (this is a 2005 instance).

Thanks again anyway, good to know my thinking was along common lines.