I finally found the isssue. We had a PreReceived hook on Github that would check if branch names are created with a specific prefix. It was preventing github silently from creating the branch for the merge queue (gh-readonly-queue/*)

After allowing the prefix, everything was working fine

PS: this issue also occurs if you use the rulesets feature in github to ensure specific branch name, so you will need to add the prefix in this feature too