Yeah, the data size is a big problem, but the bitcoin dev team is working on a bitcoin-lite client to solve that problem. Their eventual solution might be repurposable for bitmail.
And here's another thought about that - just delete all messages from the blockchain after they're read, and only store them locally in the clients. As soon as the receiving client unencrypts the message, store it locally, then delete it completely from the blockchain. Unlike bitcoin, this wouldn't be an accounting ledger with the necessity of storing all transactions in perpetuum. All that needs to happen is the message get delivered to its recipient, once that is verified to have happened, it can be deleted. The clients can keep copies and organize them into conversations or whatever.
That wouldn't quite solve the issue of hardware eventually being able to brute force the encryption though, since an interested party could store a running record of everything put into and deleted from the blockchain. But it would have to be a very interested party to store that amount of data in the hopes of being able to decrypt it years or decades later.
Bitcoin wasn't really designed for deletions though, and that would also double the rate of blockchain diffs, so would have to think more about how or if that would work...
A small marketing firm I happen to admin the email servers for... sends 15 million marketing emails per month (all opt-in, CAN-SPAM / Australian Spam Act compliant). This alone is nearly 1.5TB of data. We only send marketing campaigns for about 8 national brands and about the same number of regional brands to a country of twenty something million people.
Now It might be suitable for a conversation or private chat room. It would work really well in an IRC / small group situation. But I can't imagine a single global system ever scaling past a few dozen people without some significant hardware.
As far as deleting things, the problem there is who is responsible for deleting and what if I don't? The number of bounces we get from campaigns from defunct mail boxes that have filled to quota is quite high. Who removes this email that no one reads? At the moment the storage problem is isolated, but a central chain makes it impossible.
The more I think about this makes me think you might get it to work with a block chain per domain... but then whats the point over simply setting up your own email server you trust and using encryption?
Actually if you go with the concept of pointers to messages detailed here http://news.ycombinator.com/item?id=3615862 you enormously cut down on the size needed to store those messages (one message with a million recipients is just one message + a million recipients, not one million copies). Also with regards to deletion you could leverage the economics to pay for size, for example a user with a 1tb mailbox store will have to pay more mailcoins than a user with a 200kb mailbox store.
The pointers method is used by most commercial mail archival software that I've seen (the kind big companies deploy for SabOX compliance).
The problems with Pointers & de-dupe is that at least marketing emails are personalised, each are sent independently often with at least a minimum of personalisation, for example calling you by your name (people are more likely to read it if it calls them by name). You can do de-dupe, but your limited to the efficiency and overhead of your block size. Compression would also take the storage required down to ~ 1/10th (excluding attachments), but I don't think thats still enough. Even if deduping and pointers gave you a 500x storage saving, the data size for a few days email is still so unfathomable that it won't work as a single global system.
As far as trying to solve it with economics, its been tried (as a method to stop spam) but the question is who has to pay who and for what? Every such scheme has failed because you end up missing one of the big groups of users as it becomes un-economical for their mail pattern to continue. If you make the senders pay, few comercial entities want to play, and few people will provide free email. If you have to pay to store then how do you stop being billed for someone flooding you.
I think if we throw away the direct similarity between the blockchain as a transaction log vs a spoolchain as a massive collective megaspool and instead go with the concept of a spoolchain being a log of pointers to storage bins which are the actual distributed storage for a destination group, we get rid of most of the problems with storage size.
Eg. I am email@example.com, I want a storage bin for this account. A storage bin could then be either someone who just has firstname.lastname@example.org (say on a massive scale, the u shard for the provider.com domain) or someone who has the entire storage bin for provider.com, or someone who has the entire storage bin for .com
Couple this with open access to the storage bins from any and all (the more the better, the heavier replicated they are the easier / faster end users have access to their mail) and an economic incentive to participate in storage propagation (mailcoin? n mailcoins per n mb of storage, charge mailcoins for access to the storage bin, whatever model makes the most economic sense) and we might be onto something. It also handles deletion and allows users to "un-send" mail by deleting the mail from the storage bin it exists within. The blockchain in bitcoin does not allow for transaction deletion operations, but that does not by any means rule out the possibility of deleting the position in a storage bin where the spoolchain in mailcoin points to.