I had to resort to a very bad solution.
I am now generating slugs on frontend, checking them if they exist on Strapi and regenerating it again if it does and again checking. The first name is used to generated a slug followed by a digit depending on the result returned by checking. It’s a very bad setup. Wish Strapi’s system for unique slug/username generation wasn’t this broken. Surprisingly it all worked in the previous version.