Successes are on 18.04.3, failures are on 16.04.6 and 18.04.4.
Googling suggests that this happens if there is a breaking change between OpenSSL versions used to encrypt and the one used to decrypt:
I must also note that aes-256-cbc doesn’t seem to be a documented openssl subcommand.