Making Use of the Target Values for Regression
Clustering is definitely something that can help. As you describe, the issue is that you can see that not all instances "behave" the same way. So if you can cluster them into groups that do behave more similarly, you would probably improve.

Any clustering technique would work in theory. Although, techniques like K-means for instance do favour clusters of even-size, and so if your problem isn't necessarily "balanced", I would be cautious.

What you could also do to improve your clustering is to look at which features are more discriminative (perhaps look at the information gain) and use a weighted distance to favour these features.

Another way I feel could help you is if you used meta learning/stacking. By that I mean that you could use decision trees to split your data in a supervised way (as opposed to clustering), and at the leaves, use a more elaborate regressor than majority voting.