There isn't a problem with storage but there is a problem with the computation time necessary when constructing spend transactions which involve a large number of inputs from your wallet.
This is a problem that is evidenced by those who run Martingale betting bots against SatoshiDICE for instance. After they get several thousand bitcoin addresses with transactions, their subsequent bet transactions that draw from those coins start to crawl.
A future release of the Bitcoin.org client will address this by switching from BDB to LevelDB. Additionally targeted for future release is "ultraprune" which will lessen the storage requirements as well.
In the meantime, InstaWallet is one service that was able to come up with a solution that mitigated the problem. They might be able to offer some suggestions.
From what I heard, Bitcoin uses a hash table for storing its addresses when checking new blocks and transactions for whether they are related to our wallet or not. This data structure should allow for fairly efficient data handling, meaning that it should scale fairly well with growing amount of addresses.
So, for any sane amount of addresses, Bitcoin should scale well. Generally, the size of the wallet.dat is small in comparison to how much RAM even a low-end machine has, so it shouldn't be much of an issue.
http://bitcoin.stackexchange.com/questions/4928/how-many-addresses-can-be-handled-reliable-in-one-wallet
