I submit it is not guesswork (assuming no server load/blocking issues). It is what I call the "widely-varying-input" problem. Pay attention to that I am about to say, because it is a MAGIC BULLET for that class of queries (which is essentially ever report query ever written with start/end dates or a date comparison, and also situations where one "identifier" can get a few rows and another get 40% of all data, et al):
IF YOU HAVE WIDELY-VARYING INPUTS TO A QUERY (see above indicators) YOU ABSOLUTELY MUST ENSURE SAID QUERY HAS OPTION (RECOMPILE) ON IT!!!
You can't POSSIBLY want the same query plan on a query that has @StartDate and @EndDate when the first execution has yesterday and today and the next execution (using that stored query plan) has 19000101 and 99991231. The opposite order of first/second calls kills you to, just with a different plan.
The above thing alone has made me look like I am a magician at MANY MANY clients.
Since he's running it from an Access front end, it sounds like an ad hoc query and therefore he shouldn't be seeing plan reuse at all, should he (except maybe with the same arguments for the dates)?
Edit - of course the only way to know for certain is to look at the plans.
John