My questions: how do I know that I have to apply decoding more than once

You have to deduce that from the input yourself. There's no way perl could know it for you.

However if you have a sample of the input, the same sample correctly decoded and an idea what encodings are invovled, my module Encode::Repair can help you.

and why different utf8 decoders behave differently in perl?

Encode::decode is a high level API, and thus does extra sanity checks that the low-level API does not.