@Brenden, to many results isn't the issue in my case. Page 11 should be results 101-110, way under the 1000 result limit. I did add the Web.config key as we will likely need it, and am getting the same results as before.
Looks like I needed to add
searchParameters.NumberOfProcessedResults = 3000;. NumberOfProcessedResults is 100 by default it seems.