It's correct, but so is your line of thinking. These things are not impossible, they are all but impossible. And all in this context includes things like requires an expert, is highly hard to do, and/or would take many years. It is all of those things, but not impossible, hence all but impossible.

The idiom "X is all but Y" means "X is very nearly, but not quite, Y." I think of it as "X is in all ways like Y except one last little bit."

> is "all but impossible" correct?

Yes.

> whenever i see the "X is all but Y" phrase, it makes sense to me that X is not Y.

It's not "X is not Y", it's "X is all but Y", that is, X is very nearly not Y. "All but impossible" means it's possible, but only barely.

And to make it extra confusing there's "X is anything but Y" idiom which basically means what pvinis says.

aaah thats why i get confused. i thought its always one phrase, but its "all but" and "anything but". now i get it. lets just say this whole confusion is anything but unclear now. it used to be all but impossible to understand what people meant.

Oh, I didn't realise that either. Now I understand.

All but impossible means nearly all the way to being impossible.

Nice explanation at http://grammarist.com/usage/all-but/

It's an exaggeration where the upper bound isn't met.

All but impossible, it's everything up to, but not including impossible.