...
Their org has more than 2M records so when salesforce runs the table scan it reaches the limit of the final threshold - 600k. GuideDogs has more than 600k+ thus making the query unselective.
...
https://resources.docs.salesforce.com/rel1/doc/en-us/static/pdf/salesforce_query_search_optimization_developer_cheatsheet.pdfTo make the query passable and successfully update the Gateway API key, you need to contact Salesforce and request to Index the possible fields inside the query (e.g. Payment Status).