By ridiculous I mean something absolutely absurd. 1 million+ addresses. Like say if Amazon had started to accept payments, how could they possibly keep up? Bitcoind probably can't keep up? How would I go about solving this? How does SatoshiDice or Blockchain deal with this?
There's absolutely nothing you need to do per address, so the number of addresses has no effect. You only need to process each transaction.