Agreed, to me the meaning unpacks like: "it meets or exceeds every category of difficulty that is less severe than Impossible."

Compare to a disaster described as "the destruction is all-but-total".

That phrase does not mean "you could describe the destruction by any label except total." For example, whatever just happened it definitely not "tiny" or "moderate".