So Ola himself graciously gave me the solution to this issue that worked.

Instead of calling the stored procedure from a T-SQL job step, the stored procedure should be called from a CmdExec step, using SQLCMD and the -b option.

Example:

sqlcmd -E -S $(ESCAPE_SQUOTE(SRVR)) -d DBA -Q "EXECUTE DBA.dbo.MultiStageFullBackup @databases = 'USER_DATABASES', @Directory = 'Z:\', @CleanupTime = 732, @NumberOfFiles = 20, @LargeDatabaseSizeThresholdMB = 20000;" -b

When performed in this fashion, the backups behave correctly.