Came across this same issue on macOS version 13.5.1 and above. Worked with support and did some additional testing and came to a consistent solution/fix.
Following the steps for creating the escrow recovery certificate, if you don't have the previous private key and public pem pairing. Make the output certificate file .der rather than a .crt then rotate out the certificate and profiles accordingly.
You will have to decrypt and re-encrypt your devices after it's pushed for the FileVault key to be successfully escrowed, but could run some FDE terminal commands or script to do this without having to interact with the end users.