Thanks for including that information, David. I went ahead and copied Emily on this discussion as well.
After looking over your Workflow Definition, I believe I know what's going on here. We have this outstanding issue which has been around for quite some time that needs to be addressed in order for a Publish Set trigger to be able to execute after a Deletion in a Workflow.
If you reproduce the issue in your environment and then look over your cascade.log file, I imagine you'll see an error similar to this:
Non fatal error occurred executing trigger com.cms.workflow.function.PublishSetTrigger: Needs an attached entity. This workflow could not fetch entity with identifier: [id=xxxxxxxxxxxxxxxxxxxxxxxxxxxx, type=page]
which would confirm that this is the exact same problem.
Unfortunately, there isn't any great workaround for this at the moment. In general, I believe we've recommended that anyone who happens to be running into this may want to schedule a Publish Set to be published every 'x' hours just to keep the site fairly up-to-date after these deletions occur.
I'm going to move the related issue up in priority since it has been around for some time and I can definitely see why you would want to perform these actions in the order you have them.
I apologize for the inconvenience in the meantime.
@c-schwarze @e-jameson @d-freed
From HH on our help request: