Thought of a way to squeeze both a 64 byte previous message hash and a 64 byte signature into a message, using only 64 bytes.

Just leave out the previous message hash from the serialized message, but include it in the data that's signed. When verifying the signature, try recently seen messages's hashes as the previous message until finding the one that makes the signature verify. (Conveniently, Ed25519 verifies very fast and can do batch verifications.)

Ah, math..