Does changing the parameter search space after nested CV introduce optimistic bias? Suppose I am fitting a Ridge and I decide to search a parameter space for c:[1,2,3]. I perform nested CV on my whole dataset and find the performance not so great. I therefore expand my search space to c:[0.5,1,1.5,2,2.5,3,3.5,4]. 
Can I just repeat nested CV now and expect a fair estimate of generalization error?  If not, what to do?  It seems that I have changed my parameter space (which is a part of the modeling process) based on knowledge I now have from using the whole dataset in nested CV, and therefore need to evaluate on a dataset external to my current dataset rather than using nested CV on the same dataset.  I am not "choosing" parameters explicitly based on the test data, but I am allowing for their choice based on the testing data.  Should I perform nested CV on a subset of the data to find good parameter spaces and then repeat on the full data?  It seems that doing so would still allow the algorithm to see some of the data while choosing parameters and in worst case that "some" of the data randomly finds its way into every test fold upon repeated nested CV.
For CV to give an unbiased estimate, every step of the modeling process must be repeated independently in each fold. Isn't selection of a search space for hyperparameters a "step" in the modeling process?
 A: First of all, you are right that the choice of search space is a (though somewhat indirect) modeling choice and thus any data that you use to arrive at this choice was used for training. 
However, you could have gotten around this issue by finding with the inner CV that the performance was not great, or e.g. that the optimum is at the border of your search space. In that case, you could have widened the search space in the inner CV and the outer would still have been independent of that change in the training procedure. OTOH, if the inner CV and optimization (as far as you can tell from within) look nice, but the outer CV is terrible, then you know you ran into severe overfitting. This probably means that you'd need to completely rethink your approach.
Also, you could formulate the hyperparameter tuning in a way that is still more automatic: if the apparent optimum is at the boundary of the search space, search space should be widened in that direction. Or, once you roughly locate the optimum, perform a finer search there. If you go this direction, you'll soon reinvent typical numeric optimization algorithms ;-) 
However, the drawback in our context is that the variance on the performance estimates and limits the possiblity to make meaningful comparisons. Increasing the number of models that are compared, you also increase the risk of skimmig that variance, i.e. overfitting: you pick models that accidentally look well with the given test sets. 
