My approach to this has been to embrace, extend, extinguish (yes, that was an intentional reference, sorry):
Insert a constrained API "around" the service you can't modify. Change all your services to go via that API instead of direct. Now you can apply the fixes you can to the new layer while finding ways to gradually replace it in parallel.
At the same time the new layer provides a constraint: It should be as narrow as you can get away with - creating a "new contract" with the API consumers about what they're actually allowed to do without negotiating with you, and ensure that any expansion of dependencies on the service you can't touch get documented and appropriate attempts made to avoid increasing complexity (it's good to do this in general, but realistically it's easier to get buy-in to enforce in limited cases like this).
This intersection of tech with procedures and politics lie at the heart of a lot of technical architecture work. A huge proportion of the work we do is not technically hard in and of itself - it becomes technically hard because of organisational considerations.
It isn’t a technical problem...