I have encountered something similar before, and spent some time trying to get to the bottom of the problem, using SQL Profiler, and watching the query run by the user, then repeating the query from Query Analyzer. The only explanation I could come up with was:-

SQL Server stores query plans according to the 'SET' options in force at execution time (e.g. ANSI_NULLS). The users may come in with different 'SET' options than you would when running the query via Query Analyzer, and therefore SQL Server will store more than one plan for the same query.

It's possible that one query plan will have decided not to use an index (because at the time is was cached, the WHERE clause had a parameter that made using the index pointless e.g. SURNAME='SMITH'), whereas the other plan will have used an index (e.g. SURNAME='WILKINSON-JONES'). Once the plans are cached, they will get re-used, even though the parameters are different.

Rather than re-cycling SQL Server, I did a DBCC FREEPROCCACHE to force SQL Server to generate a new plan, which had the desired affect, and the queries started running quickly. Using DBCC FREEPROCCACHE, unfortunately drops all cached queries, so I also tried a slightly less drastic method of doing an UPDATE STATISTICS on one of the tables used by the queries. Again this had the desired affect.

Of course, I may be talking complete !%&%$"* in my assessment of the problem, but the action taken to solve it worked!