I work for a company that creates software that interfaces with Sharepoint using Web Services. We have run into an issue at a few clients where we are hitting the threshold limit on document libraries that contain records greater then 5000, even though our query is only returning a few records. It was my understanding that you would only hit the limit if your query or view returned 5000 or more records.
Here's an example of a request using the lists.asmx web service.
var libID = "{97769110-C075-4BB8-93F3-8FD97A1C5AEB}";
var viewName = null;
var xnodeQuery = "<Query><Where><Eq><FieldRef Name=\"BATCH_NO\" /><Value Type=\"Text\">123456ABC12345</Value></Eq></Where><OrderBy><FieldRef Name=\"Created\" Ascending=\"False\" /></OrderBy></Query>";
var xnodeViewFields = "<ViewFields Properties=\"True\" />";
var xnodeQueryOptions = "<QueryOptions><IncludeMandatoryColumns>FALSE</IncludeMandatoryColumns><DateInUtc>TRUE</DateInUtc><ViewAttributes Scope=\"Recursive\" /></QueryOptions>"
var xListItems = listService.GetListItems(libID, viewName, xnodeQuery, xnodeViewFields, "", xnodeQueryOptions, "");