concurrencyPolicy: Replace is working, but it is kind of ugly. Kubernetes never recognizes jobs as complete and cluster resources are used to keep containers running that are doing no useful work.
In an IRC conversation @Joe mentioned the idea of using the spectacularly named POST /quitquitquit endpoint of the envoy service to signal it to terminate. A POST to localhost:1666/quitquitquit could be added to a runner script that the CronJob executes to implement this. It may also be possible to find a Kubernetes lifecycle signal to attach it to, but that needs further investigation.