Is there such a thing like the machine learning paradox?
Basically Machine Learning is used to solve problems for which giving exact solutions is not (practically or theoretically) possible or feasible. If you have a problem that can be solved with exact and proven methods, you don't need Machine Learning. So Machine Learning is rather about finding solutions by approximations with some error margins. In this sense such systems will never perform perfectly and there always will be room for improvements.
(Many real world problems can not be solved perfectly because they are not simply complicated, but chaotic.)