My old core2duo cpu able to decrypt ECC + AES at 100messages/sec (first solution) and AES over 10000messages/sec (second solution), so I don't think its going to be a problem. Every site in zeronet is totally independent, so if the updating/verification become problematic anyone able to clone the site and creating a new network of messages.
To solve this we could add fixed prefix to the encrypted text, eg.: os.urandom(16)+"ZNE1"+message
The random needed because according to stackexchange it should be avoided to start the messages with same text. (we going to use AES CBC mode)