Unfortunately I would need to see more info to really help with this. It's not a standard or known problem with a well documented solution. Could be a million things.
For now, can you ask that client to run a full stats updates on any tables that those selects affect?
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