Doesn't the public key have twice the size of the private key that it's derived from? (I remember something about that, but I'm not sure.) If so, yes, most byte series will never appear.
Not really; both the private key (scalar) and public key (point) are encoded as 32 bytes. However, some implementations concatenate the two and refer to that 64-byte array as the "private key" -- this is simply an optimization so that the pubkey doesn't need to be re-derived each time you want to compute a signature.
The point was about public keys, not private keys. The answer then is going to sound similar, but is in fact entirely different: the public key is often specified as the X and Y coordinates of the point ("uncompressed"), but only the X coordinate and axis disambiguation is required ("compressed").
there are many times more public keys than there are 5 byte prefixes. I don't know much 25519, but there is no a priori reason to suspect his brute force won't succeed.
