Dealing with an apparently inseparable dataset
You might have a domain adaptation problem.
The samples are actually taken from two different sources and have different rules governing their behavior.

I suggest that you'll try the following method.


Split the data into two data set using the target concept.
Build a model for each data set. In case your performance doesn't improve it is likely that the domain adaptation assumption is wrong. 
Otherwise, we gain an improvement. Now we should find out which model to apply. Use the full dataset and use the target in order to create a new concept indicating to which dataset the sample belongs. Since you said that given the target you can deduce that I assume the two are different.
Build a model for the new dataset. If it performs well, the problem is solved. Run this model first and apply the proper model for each sample. Otherwise, it means that the two data set are indistinguishable (at least with respect to the methods you applied), weakening the assumption the the cause of the problem is domain adaptation.