The apparent contrariness of the meaning of this term has often intrigued me, so I thought I'd do a bit of light research on it.
Wiktionary defines it as follows:
all but (not comparable)
1. Very nearly.
The food is all but finished.
Now, I think that when most people encounter this term, they want to interpret it more as a negative. For example, "The food is all but finished." might be interpreted as:
The food is everything except finished.
However, reverse the two words and it starts to make a lot more sense in terms of the standard meaning. (Even better, replace all with totally.) In other words, the sentence is actually to be interpreted as:
The food is but totally [all] finished.
In this slight rephrasing, it is (to me) much clearer that the term
all but actually means almost or nearly. Why the words all and but got reversed, thus obscuring the true meaning. I do not know, but I hope this is partly enlightening.