If you gave this service a dedicated, non-co-located fleet, running the JVM directly on the OS, and ran basic autoscaling of the number of hosts, you'd eliminate a huge number of the moving parts of the system that are causing these issues.
Yes, that would add to ops costs (edit: human ops costs) for this service, but when you're spending 8 figures per year in it, clearly the budget is available.
To quote the great philosopher Avril Lavigne: "Why'd you have to go and make things so complicated?"