The problem with paradoxes is simple. If you throw out any theory with paradoxes, you can start by dumping :
-> big bang theory
-> quantum mechanics
-> relativity
-> newtonian physics
There wouldn't be much left :
Indeed if scientist respected the laws of mathematics there would be no paradoxes in physics. Any theory containing even a single paradox would be thrown out the window immediately, like they are in mathematics. You could simply say time travel has the potential to create paradoxes ... and is therefore impossible ...
It wasn't to be : It wasn't very practical with physics theory. After all, the big bang theory requires FTL travel (faster than light) and a "limited" suspension of at least causality, along with changing a few universal constants here and there (in fact even Genesis is more likely : suppose an "eternal" being, alive or not created our universe, and you don't have any causality problems. Who created the creator ? Nobody, he's always been. Mathematically that's simple to express and quite consistent. Of course the 7-days stuff of Genesis is a bit more problematic). Oops. Physicists weren't quite ready to dump that one.
Newton's physics would be thrown out, due to the black body radiation paradox (has nothing to do with black holes). But as long as nothing was there to replace it, nobody really thought throwing it out was a good idea.
Relativity would get thrown out due to Schwarzchild geometry (black holes), and quantum mechanics would get thrown out for a hundred reasons, it's "known paradox count" is somewhat of an embarrassment really.
So physics just "tries to get along" with paradoxes, which never works in practice, so basically experiments just like to get close to paradoxes, because in the real world they don't exist. Therefore the paradoxes we're seeing in theories are really something that's not described, rather than a real paradox. Sometimes we really can't get close enough to take a look, which is the case with black holes, or the edge of the universe (if there indeed is one, like the big bang theory predicts), in that case we're stuck, and the only option is to search for the needle in the haystack some other place.
That obviously brings the problem which paradoxes are acceptable and which aren't. Nobody's given even a basic answer to that one though. Apparently paradoxes are acceptable as long as they only manifest in places we know nothing about.
Paradoxes are also the real reason for the claim "passing through a black hole makes anything possible", which is simply another way to say that once you've proven 1=2, you can prove anything, no matter how wrong. Of course the problem is in our understanding of black holes, which is mathematically inconsistent, the problem is not that inside black holes anything is possible. Same goes for any other paradox in physics.
Of course many people believe that since there are many "paradoxes" in physical theories, especially quantum mechanics, everything is really possible, if you only think hard enough about it. However history does show us that every single time we approached a paradox in experiment, it turned out our theories produced the paradox, and the world disagreed with our theories.
You can resolve the black body paradox of Newton's theories yourself. Google the "black body radiation problem" (the third link is nice). Then heat up a piece of metal until it glows. According to Newton's physics if you do that, the universe should explode (calculate this for yourself). Or to put it mathematically, the energy output in radiation should "approach infinity", which is another way of saying "this should produce a huge bang". There you've just explored one of the great historical paradoxes. All paradoxes are like this.