Yeah, this is something that has always bugged be a tiny bit. I was more familiar with the idea of a paradox as something like your definition -- containing an actual contradiction. But it seems to be used instead to describe any initially counterintuitive situation.
It is tempting to attribute this to a technical/non-technical difference (similar to fallacy, which in non-technical discussion has been expanded to basically include almost any bad argument). But somehow the Birthday "Paradox" has managed to stick in probability.
Paradox isn't synonymous with contradiction. Some paradoxes are, or contain, logical contradictions (i.e. they effectively say both X and not X are true) but the term is much broader.
Some of the earliest paradoxes are Zeno's, and they were referred to by that term at the time. For example the paradox that an object that moves towards a point must first cover half the distance, and then half the remaining distance, then half of the remainder, etc. Since this is an infinite number of steps, Zeno playfully argued that motion is impossible. There's no logical contradiction there, just a way of pointing out something counterintuitive about reality and maths.
That's fair, the thing I'm looking for isn't quite a contradiction.
What I like about Zeno's motion based paradoxes is they have this aspect of "here's a reasonable model of motion, and here's the ridiculous result you get from it." There's clearly something wrong in the model, but working it out takes a while, you need someone to come around and invent series first.
After a little reading, I think I just like falsidical paradoxes and don't like veridical paradoxes.
Huh, what are the odds that the same mathematical concept will come up in conversation twice on one day? We have invented the Synchronicity paradox, er, problem.
It is tempting to attribute this to a technical/non-technical difference (similar to fallacy, which in non-technical discussion has been expanded to basically include almost any bad argument). But somehow the Birthday "Paradox" has managed to stick in probability.