So the addresses are public like Bitcoin addresses that have spent coins are public?
Doesn't sound like a issue with the Bitmessage network.
However about the scaling issue, is that going to be modified or not? Any chance Bitmessage could scale to a billion messages a day?
I'm just guessing here, but I would think that the network should scale better with usage. Flooding the network with messages without increasing the number of users running the client might not be best stress test of scalability. The two things from this that are of concern RE: scalability though are SPAM potential of public addresses and intentional flooding of the network to slow it down (kind of like a BM DDoS attack). SPAM is a very hard problem to solve in the email world, and anti-spam is literally a billion dollar industry. I don't think the equivalent could develop for BM without compromising security.
All of that said, it seems like a simple solution could solve all of these problems: require a hashing PoW function as part of a message send. The original Hashcash algorithm that the bitcoin hashing algorithm was based on was designed for this purpose. Maybe this is how BM works already? Doubt it though, I'd think it would have been a lot harder for him to send all of those messages out if it was.