I was just talking to some vendors about this at a conference recently (yesterday). One of the ones that really caught my eye was TopDesk. I don't know if they support on-premises deployment or not, but I think the others might check the right boxes. I have no idea on pricing, but I believe they were the ones that do their licensing based on FTE count (due to having a broader focus than just ITSM).
Not one that I've heard of before.
There were quite a few that were there that I'd not heard of. This my first interaction with them. They've been around for quite awhile. It may be that they're more well known in the European market since they're based in the Netherlands.
Their back end for the hosted system is written in Dutch but they do provide some kind of translation ($Dutch_word = $English_word) so you can poke about. Also, they (TopDesk) must do the software upgrades (logging in remotely and doing the work). Not your team.
They also now have a SaaS version but that's not one of the OP's requirements we couldnn't get away fast enough.
(I inherited workig with it).
@nadnerB Are these issues that linger with the current version, or not? It would definitely remove them from the running if they persist.