So I have found the problem and it seems to be a Twitch problem.
I rechecked my application’s client-id and the redirect url on Twitch and I found a new dropdown box “Application Category”. This dropdown box was not there when I initially registered my application. So it was empty, no entry selected.
I selected a proper entry (Application Integration) and suddenly me and all my users could authorize again… Weird stuff that Twitch developers might look into.