I wonder about the spam problem as well. Blocks will not work.

I have a feeling that Hashcash could be a solution, and where instances do not participate in it you could slow their connections in. Just an idea though.