Alerts are broadcast in the same way as transactions. Each node, upon accepting the alert, sends the alert to all of its peers.
Bitcoin won't relay alerts that are signed with a different key. Propagation might not be very good for any client if different alert keys start being used.
That doesn't sound very scalable... Does anyone remember the gnutella bottlenecks? If not, read up on this:
http://en.wikipedia.org/wiki/Gnutella#DesignAlso not relaying alerts signed with a different key basically means there's only one person in the whole world that can send messages through the network. Isn't that kind of against the spirit of p2p and decentralization in general?
The Network as it is right now appears to be a random graph with fixed node degree (8 connections each host), this indeed will never scale, and we have to find a better structure. eDonkey and others fixed it with a two-hierarchy network with supernodes and nodes, while this might solve some issues I don't think it's perfect. I'd rather go with hypercubic networks as they are truly P2P and have no single points of failures.