New Apex Batch Jobs always end up in the flex queue in holding

In case anyone else ever has this problem in the future, you have to contact Salesforce support and (if you don't have Premier Support because you can't submit Apex issues) convince the agent to escalate this for you, explaining you need to remove any ApexToken jobs which are stuck in the queue. These are visible through a query, but not in the UI, and we (users) can't remove them.

SELECT Id, JobType, CreatedDate, Status FROM AsyncApexJob WHERE JobType = 'ApexToken'

Once this was done, the jobs started as expected.

There was a developer forums post which helped identify this issue: https://developer.salesforce.com/forums/?id=9060G000000I4EzQAK