Standard (non-normalized) conformal regressors produce intervals that are of identical size and hence non-informative in the sense that they provide no information about the uncertainty at the instance level. A common approach to handle this limitation is to normalize the produced interval using a difficulty estimate, which results in larger intervals for instances judged to be more difficult and smaller intervals for instances judged to be easier. A problem with this approach is identified; when the difficulty estimation function provides little or no information about the true error at the instance level, one would expect the predicted intervals to be more similar in size compared to when using a more accurate difficulty estimation function. However, experiments on both synthetic and real-world datasets show the opposite. Moreover, the intervals produced by normalized conformal regressors may be several times larger than the largest previously observed prediction error, which clearly is counter-intuitive. To alleviate these problems, we propose Mondrian conformal regressors, which partition the calibration instances into a number of categories, before generating one prediction interval for each category, using a standard conformal regressor. Here, binning of the difficulty estimates is employed for the categorization. In contrast to normalized conformal regressors, Mondrian conformal regressors can never produce intervals that are larger than twice the largest observed error. The experiments verify that the resulting regressors are valid and as efficient as when using normalization, while being significantly more efficient than the standard variant. Most importantly, the experiments show that Mondrian conformal regressors, in contrast to normalized conformal regressors, have the desired property that the variance of the size of the predicted intervals correlates positively with the accuracy of the function that is used to estimate difficulty.