I would assume the people bothered by an increase in byte-sized overhead are not the ones that are using 2^32 length strings.

About the cache, I think for small strings, scanning the whole string may still be faster.

Though adding a four-byte length prefix would make certain functions like strlen almost go away.