Just to double check: "already checked that" as in spied on it actually running (e.g. using SQL Profiler) from the APP to check that the query for that, empty, recordset does not take SQL "longer than reasonable" and also "does not use a daft query plan"?
Doing a synthetic test in isolation can fail to show up user-related issues. Two that spring to mind are parameter sniffing and things like, for example, absence of Schema prefix to table names causing Parser to examine if there is a user-specific table/view available instead.
If you already know all this stuff then apologies and please ignore 