I used cross validation on my data (11000 rows) with maximum salary of 10000 and after some cleaning I got to rmse=70. Then I tried to remove the outliers 10 times just to try things now I have 9000 rows with maximum salary of 260, I got rmse=23. Is what I did bad even though I got a better rmse? Is the jump from 10000 maximum to 260 a bad thing? Is the jump from 11000 rows to 9000 a bad thing?
Removing outliers is only appropriate when you have reason to believe the data is wrong. Do you have such a reason? Otherwise, you are, as @Dave suggested, tricking yourself into thinking you have good predictive power.
If your data is not "nicely" distributed, and you're having trouble fitting a model to predict it, the first thing I would try is transform the
salary field to a more usable range. For example, you can try predicting
sqrt(salary), then transforming it back if necessary.
Your data is distributed very strangely, to say the least. A mean value of 178, stdev 225 and %75 is 176 is probably as far from a normal distribution as possible. But it is probably a good idea to get rid of anything out of 3 standard deviation from your mean value, that is 178 + 3*225 ~ 853.
There are different ways to deal with skewed data, but for your case it is probably best to get rid of some outliers. But as @Dave points below, this lowers the predictive power for extreme values, so it is more of a judgement call.