Filtering on an Indexed field in a large list counts recycle bin items
This is a behavior I thought I'd point out, in case anybody is running into it without knowing the reason, as it may not be intuitive... :-)
If you have an indexed field and are filtering by it, but it doesn't work even though you are positive the list doesn't have more than 5k (or whatever you set your list view threshold to be) items that fit that filter, then you might want to check your recycle bin for items. If the total number of items that fit that filter on the indexed fields, including the recycle bin items, is greater than 5k then you are hitting the list view threshold and may get an incomplete set of results, or none at all.
Items in the recycle bin aren't really deleted from the database, so they still count when the pre-scan query runs to figure out how many items need to be queried to find the ones you're asking for.
Hope this helps!