From the sounds of it, you may be experiencing a thing called "Parameter Sniffing", which is usually a good thing, by the way. Sometimes it causes a bad plan to be selected, though. There are many "fixes" for such a thing and what the bad Parameter Sniffing is and how to fix it appear in many articles and post. Just Google for "Parameter Sniffing".
--Jeff Moden
Change is inevitable... Change for the better is not.