Observations with same feature values but different Classes Observations with the exact same attribute values should also have the same class value (basically the mapping to learn from data). If this is not the case, then there are not enough attribute measurements (assumption).
How do you treat this problem in preprocessing steps if your dataset is fixed?
Would you just remove both instances and call them outliers? (with the necessity to analyse why that happened)
 A: Don't worry about it.
ML methods tend to be robust against that kind of thing in the training set - roughly speaking. They will cancel each other out, but perhaps not exactly.
If the occur in the testing set they place an upper bound on your accuracy, since you can't guess both.
But that is fine. It may be good to report a theoretical upper bound on the accuracy in these cases (though I've rarely seen it done.).
If regressing to class probability (like in logistic regression), you can do well at minimize the loss function (e.g the cross entropy between your estimated distribution, and that observed in the test set). And thus get a useful probability estimate as your output.
A great many problem are such that your input data does not fully capture enough information to predict the output.
I've worked on problems where there dozens or hundreds of different label classes for identical features.
Multiple different output values  for same input values
is ubiquitous when talking about using ML for regression.
A: I see this problem in following way with following solutions:


*

*If attributes are the same, but classes are different, then probably you are missing some attributes that actually tell the difference between classes. So you might need more domain expertise, feature engineering and/or data collection.

*Model will assign the most probable class to such instance in test dataset. If this instance indeed appears more frequently as one of classes, then it is more probable to be this class. If you leave it as it is, it might work well, but you need to experiment with it.

*Or, sure, one of solutions is just removing those cases from dataset.


Also remember that there could be a human error because of accident or lack on knowledge while creating dataset. So, again, more domain expertise might help.
Note: try different solutions separately or together. If it works, it works. Even if it is weird.  
