I think that it could be done better. .NET's CancellationTokens are a step in the right direction, though sadly just one step. You can check if cancellation is requested, but there's also a method for asking the token to throw a CancellationException if cancellation has been requested, and this is how all the abstractions around threading do it.

But it's reasonably easy to imagine ways to produce an API that only uses tokens like that instead of using exceptions to signal cancellation/termination requests. And I suspect, given how many bits have been spilled trying to explain to people just how they're supposed to deal with InterruptedExceptions, that the resulting system would have better ergonomics.

Long story short, I don't know that it's that InterruptedException was a necessary evil so much as that people were still fairly new to this whole exceptions thing when Java came out, and it's really hard to get subtle things like this right on the first try.