> Could you implement something like IRC's "flood prevention" in a proof-of-work based consensus algorithm -- so sending messages closer together costs prohibitively more?

This seems easily circumvented by creating lots of identities. Though maybe creating an identity could be costly?