Hybrid.
Notice that the current bitmessage implementation has scalability problems (and they do not seem to care).
Consider a p2p message system like this one:
Messages are divided in headers and bodies. Headers are less than 0.1kb and messages can be as large as you want. Headers contain a micro-message or they point to an id of a body or to a url. Like bitmessage, you have to generate a poof of word (POW) in order to send a message. The headers contain a 'to' address field. This can be partially filled out, or left blank.
Strong clients:
Receive everything and hold everything (for a day). They help their peers.
Mobile clients:
They have a 'light' address. They make the first n bits of their address public to their peers. Then they receive only the headers where the to address is partially disclosed and the leading bits match. The more bits of your address you disclose, the 'lighter' your address is. This is also the way to scale for a few billion people. Bodies can be downloaded similarly or even with specific id. Mobile clients never send any content to their peers, nor do they retain other people's messages.
Hybrid.
So far this is p2p. But nobody wants to be a peer of a mobile client, or they might want an excellent connection to one peer. This is where more central services come in. They accept payment for a connection and provide high-speed. They also accept the useless mobile/light clients. Also these services could calculate the POW for the light clients.
What happens if one or all such services go down? Not much, because the services were just high-speed peers. The network can continue as a normal p2p network.
I have a lot more ideas on how to improve this design.