Three major challenges here:
1) broadcasting of the transaction would in many cases be just as resource intensive as sending your original message in the first place.
2) even if you got the money back there would still be fees
3) Creating dust ultimately means you will be spending these outputs (and paying higher fees) along with some of your other addresses and thus compromise your identity.
I spent a long time trying to find a way to make the system 'for-pay' and not just 'burn' CPU cycles... but then I realized something critical:
1) everyone needs to propagate other peoples messages to hide their own. Therefore, everyone is already doing an even bandwidth barter to simply forward the messages along. Statistical analysis can detect leaches and cut them off.
2) the proof of work should not be required as long as the bandwidth is below a fixed limit. Just like bitcoin limits block production, bitmessage can limit bandwidth consumption on any given channel/stream. With a fixed bandwidth stream and the ability to spawn new streams as necessary to balance load, the proof of work should only become a factor in times of congestion or when there is a need to compete with spam. Of course, spam is just as good as real traffic for hiding in the crowd and as long as the channel/stream you are listening on is within spec for bandwidth usage, there is really no problem what-so-ever.
They are two issues:
- privacy
- anonymity
Privacy can be achieved on the communication level with encryption and identity system(for ex. Namecoin).
Anonymity you can never achieve 100% and therefore all the time will be messages that Bitmessage was knacked and that will scare people to use it.
It is better to state from the beginning that total anonymity it is not the purpose of the project just a light obfuscation of the pseudonymous identities. It can be created a better connectivity to the Tor network or bundled editions with Tor offered. Then not Bitmessage will be blamed when identities are revealed.
A global attacker which can control great part of the internet can anyway reveal connections between identities with statistical analysis.
You can delay this with more routing traffic and delaying message delivery on the cost of the usability but you will never eliminate this attack possibility even if everybody will receive every message.
A balance is needed between usability and anonymity. Must users are complaining not about the insufficient anonymity but about the slow speed.
Who needs more anonymity can change his BM identities more often and can use Tor to hide a connection between his real identity and BM identity.