In RBAC, under the BatchJob authorizations, there is a BatchJob.Create and a BatchJob.Modify, but those are to create and modify the BatchJob itself. There is no BatchJob.CreateSchedule auth, so you are probably interested in the BatchJob.ModifySchedule auth.
Does the user have that particular auth in their roles' auths? If so, does the user also have that auth on the specific BatchJob?
Figured this out... I was missing the batchJob.modify property for the role trying to delete the schedules. They seem to need this along with the modify schedule authorisation.