This is actually a really interesting problem because depending on how you set it up, you'll get very different answers. To illustrate, notice the difference between these questions:

1) Suppose I flip a coin 3 times and repeat that experiment on 10 different occasions. What's the probability that I get all heads at least once?

2) Suppose I flip a coin 30 times (same total number of flips). What's the probability that I get at least 1 string of at least 3 heads?

(1) is more like the binomial calculation you've set up, but I think (2) is closer to the question we want to be asking.

This is important because, as it turns out, (2) is much more likely than (1). You can tell intuitively that there are more sequences of coin flips that would satisfy (2). For example "THH HTT ..." would satisfy (2) but not (1).

So how should we pose the hurricane question? I propose: What's the probability that in a 100 year period, across 100 cities, there will be at least 1 city that experiences a 500-year flood for at least 3 contiguous years?

Solving this analytically is non-trivial, but it's easy to simulate:

  // Scala

  val rand = scala.util.Random
  def coinFlip(p: Double): Boolean = rand.nextDouble <= p

  // Simulates 100 years and returns true if there's a contiguous string 
  // of three events with p=1/500.
  val targetEvent = Seq(true,true,true)
  def threeIn100Years = Seq
    .fill(100)(coinFlip(1.0/500))
    .containsSlice(targetEvent)
  
  // Simulate this 100,000,000 times
  val simulations = 100000000
  val count = Stream
    .fill(simulations)(threeIn100Years)
    .foldLeft(0){case (acc, cur) => if(cur){acc + 1} else {acc}}

  // Estimated probability for a single city.
  val p = count/simulations.toDouble
  
  // The probability it will happen *at least* once in a population of
  // 100 cities.
  // This calculates the probability if *won't* happen 100 times, and
  // then takes the complement, giving us the final probability
  1 - Math.pow(1 - p, 100)

The final answer I get is 9.5E-5, so still very unlikely, but 100x more likely than the binomial calculation.

How does the birthday paradox rely on non-independent events?

I guess what I meant wasn't "non-independent events". However, there is still a fundamental difference. The probability of a 500-year flood happening next year is still 0.2%. With a birthday paradox, the filling of birthdays is what causes the explosion in probability. Assuming no collisions so far, the 20th person you add to the room has a 19/365 chance of colliding, while the 2nd person only has a 1/365 chance.

I'm not sure how to succinctly phrase this idea. Maybe "non-constant probabilities"?

In the terms of an example:

If you put 400 people in a room, the odds that no two of them share a birthday have gone all the way down to zero percent.

No matter how many independent cities you measure flooding in, you can never achieve a perfect 0 or 1 probability of (whatever), because the cities are independent.

We don't define "interesting" flooding in one city by reference to what happened in another city, so this situation is not described by the birthday paradox.