Ola Hallengren: encrypt, but verify?
I've found the root cause and solution.

Ola Hallengren couldn't get to the back-up encryption certificate because doesn't know the Database Master Key (DMK) encryption password. The DMK can also be encrypted using the Service Master Key (SMK), which is automatically opened for a connection with sufficient privileges.

I've added SMK encryption to the DMK, which allows Ola's scripts to access the back-up encryption certificate.

I guess it only works if it's turtles all the way down. :-P