@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.
Edit:
Looks like I needed to add searchParameters.NumberOfProcessedResults = 3000;
. NumberOfProcessedResults is 100 by default it seems.