FWIW, existing users have private key files in username/files_encryption/OC_DEFAULT_MODULE/username.privateKey which are 4433 bytes long and start with HBEGIN:cipher:AES-256-CFB:keyFormat:hash: while the same file for new users is 12260 bytes long and has no such prefix.
This kind of sounds like Nextcloud change the key storage scheme without updating existing keys. Sound familiar to anybody?