Pros:

-More anonymous (harder for people to associate it with your other addresses, though not impossible unless other precautions are taken)
-Easier to identify who paid you (since every payer is given their own address)

Cons:

-Doesn't prove that you are the owner of the other address, which can be useful in trust applications
-A little bit more hassle.


Anything I'm forgetting?

The addresses are valid forever unless you lose your wallet.  The only disadvantage is that the address receiving a transaction is visible to all nodes.  It is easy to automatically generate a new address each time a page is refreshed on a donation page using the JSON RPC interface.

KSD5,

Definitely not.  I, for one, do not care about anonymity!

It would be a good idea if you have lots of people sending you the same amount.  By giving them each a different address to send to, you can tell who paid when.

oh, didn't know that.
thanks for the info!

It's not totally easy, but it's possible.  For example, a node could listen on the network and see that you are using the same IP when sending from two of your different addresses, and thus associate those addresses.  To prevent this, you should mask your IP using Tor or similar.

There's also a more fundamental risk in that the chain of ownership of each bitcoin is public knowledge.  So, if you, say, purchased the bitcoin from an exchange and gave your name during that, then the exchange can associate your name with that bitcoin.  There's a really really nice post by Theymos on that here, and the following thread proposes some great solutions (mainly, a "scrambler"):

http://bt.irlbtc.com/view/241.0

Even besides these two things, there are some other things that need to be handled.  For example, you should find a way to encrypt your traffic so your ISP can't read your addresses.  Also, you should send out identical traffic regularly, so that your ISP cant associate your addresses using timing alone.

If all of these things are accounted for, I believe you are very close to 100% safe from technical address association.

You could always pregenerate all the keypairs (addresses) you'd ever need and keep them in your wallet. Then you just pull new ones off as needed, reuse old ones as you like, etc. E.g. with every transaction you get to pick the addresses that participate in that transaction. From the network's point of view, this is is indistinguishable from the curent behaviour of generating new addresses every time, but you can backup your wallet once in some really robust fashion and never worry about backups again. You can in fact patch your client to do that right now without affecting anyone else or breaking anything. So, that's a PRO; having to back up after every transaction is silly.

The negative side of pregenerating all the keypairs is that if I steal your wallet, and you don't know about it, I can just sit around for years waiting for a big transaction involving one of your addresses and then burn you. This theft is more insidious than just spending your wallet immediately, because nobody can ever be 100% certain than someone hasn't already done it. It would undermine trust in the network.

As far as I understand, pregenerating all keypairs does not stop someone from using them
if he generates them too, by accident.
That is perceived as unlikely to happen.
But over time the number of generated keypairs will grow...
Yes, still unlikely, but still possible and nobody knows how to mitigate that.
That is an accepted risk of using the system. Just use to it. 

So, here you have accepted that risk.
You have multiplied the value of the potential damage by the probability of the event.
It is acceptable to you, because that is really low risk, since you take no damage at all.
Some may be concerned if their potential loses are larger than yours, and have not only monetary nature,
but for example, reputational damage. Bank may get slashed by a bank run, if it lose some of it's reputation,
that will be the end for the bank.

I believe that a Bitcoind address is just an encoded RIPEMD160 hash which can take 2^160 values which is about 1.46*10^48. The number of distinct public keys is vastly larger and hence many different public keys have the same address. This isn't as worrying as it sounds though.

ByteCoin

How fast does wallet.dat size grow with creating new addresses? It would be nice feature to physically remove entries from it if I'm pretty sure no one will send coins to that particular address. For example, if would be useful for shops which create one-time addresses to recieve payments. If it's used once it's not needed anymore so the shop engine sends coins from that address to a certain fixed address and removes keys for that temporary one. It will prevent wallet.dat from growing indefinitely. Also note that invisible address is created each time one sends the sum which isn't equal to the sum of a particular address or sum of several addresses so it's divided by two parts: one goes to the recipient and the other goes to your just transparently generated invisible address (you don't see it in your address book but it's in your wallet.dat). If you often send money you'd already have lots of such addresses and some empty ones. AFAIK no automatic garbage collection is done for now and it's right — there is no way to know which address is temporary and which is constant. Another proposal is to make a special «temporary address» flag which may be set on any of your addresses either on its creation or anytime later. Bitcoin checks this flag on transaction and if this (these) address(es) become empty AND the transaction was confirmed by the network (6 confirmations) then it's removed from the wallet. Hence this flag should be set for all «change» (invisible) addresses because they can't be used to receive payments (they aren't displayed anywhere).