By that token, the paradox makes some sweeping assumptions about the efficacy of interstellar communication to begin with. Space is big, and interstellar communication almost impossible unless both parties already know and are already expecting communication. Establishing first contact across interstellar distances is like trying to shoot a bullet out of the air with another bullet fired from two different guns in two different states; you'd need an exceptionally powerful gun with even more exceptional precision. And the other guy has no idea you're aiming at him. But you, the shooter, are doing on purpose; two bullets don't collide by chance. First Contact happens when one civilization already knows about the other one before hand and so they send a deliberately overpowered signal to reach out.

It's possible, to be clear, and hell it may have already happened. We just haven't been listening long enough to know.