I've had good luck with getting GitLab Issues to do an appropriate variation on Kanban, so long as I have their Scoped Labels (which seems to be in the $29/user/month Premium plan). I like the tight integration with the Git workflows, and I like not having to manage yet another SaaS.
Do some of your users need the $99 Ultimate plan, and GitLab salespeople couldn't meet you at workable pricing for your users who mostly only need to use Issues?
I don't think you can pick and choose the plans per user? We're currently using the security features of GitLab Ultimate and as far as I've understood it, that's $99/month/user for every user you need on your GitLab license.
I think enterprise software agreements can often be negotiated.
In the case of GitLab, their pricing page has the usual easy ordering buttons for each pricing tier, but the $99 tier button also has a prominent "Contact Sales" link right below the button. https://about.gitlab.com/pricing/
Once you're already paying sticker price, and have invested in using it (i.e., moving to a competitor is a lot of work), your negotiating position will be different, but the vendor can still lose the account, if customer is unhappy enough to eat the moving costs.
Do some of your users need the $99 Ultimate plan, and GitLab salespeople couldn't meet you at workable pricing for your users who mostly only need to use Issues?