I've noticed in my system, whenever a non-clustered index is used in a query that has to also do a key lookup to get the additional fields being selected, it's faster for me to instead do two queries.
The first with the non-clustered index inserting only the key field into a temp table (so no key lookup is performed) and the second using that temp table to join back to the original table to filter it down on the key and then select the fields I need.
I'm typically querying tables with hundreds of millions to tens of billions of rows when I notice this. I'm not sure if it can be related to the fact that I'm eliminating the key lookup when the table is first loaded into memory and instead I'm inserting the key into a temp table so that the subsequent field lookup query occurs between two tables already in memory?
The difference in time I'll see is usually significant too, e.g. on the order of minutes.