Still not entirely sure of the underlying logic. But it appears that sidekiq-cron does not purge jobs which are not found from the scheduled set. It's therefore required to do one of the following before a deploy to remove either all jobs or a specific one:
#destroys all jobs Sidekiq::Cron::Job.destroy_all! #destroy job by its name Sidekiq::Cron::Job.destroy "Job Name"