When querying a list with more than 2000 items, you can use the ContentIterator class which should eliminate the SPQueryThrottledException.

Don’t forget one thing: Add the columns in the WHERE-query to the indexed columns. If you don’t do that, you will still get a SPQueryThrottledException

Edit: We found out that indexed columns where not the solution either, because SharePoint throws the SPQueryThrottledException when trying to build up the indices….

We finally solved all problems by just iterating through all list items and doing our things. We could not find a proper solution, let me know if you managed to find one!