Imbalanced data for regression

I am interested in ways if treating an imbalanced regression problem.

By imbalanced regression I mean that I have few samples for some regions of my input and target space and lots of features for other regions. I don't know a priori about the exact distribution and how they contribute to the overall error. All I know that the distribution I get as training data is not the distribution I expect during the runtime of the system.

I'd be interested in ideas on how to treat this problem robustly, theoretical work as well as quick heuristics/hacks that you found work well.

So far I have been thinking about:

1. Boosting, bagging.
2. Bin the data and chose N samples from each bin (e.g. by using K-Means or some hypercube measure)
3. Minimizing a form of the squared loss, where I weigh each sample inverse to it's probability according to some model (e.g. a mixture of Gaussians) after removing outliers. Maybe a mixture of student-T's will do fine because of that.
4. Minimizing the error but only up to some constant (e.g. don't minimize below 0.05 or so),

However I have no practical experience. Anyone encountered such a problem and successfully solved it?