If I understand your question correctly, then I think for case of pairwise alignment, there is a simple explanation.

I believe the key insight is that: *a mismatch should always score better than a gap*.

This follows biologically since the insertion/deletion (indel) rate is roughly 1/10th that of the substitution rate (i.e. the occurrence of single nucleotide changes), at least in vertebrates. (This varies across the tree of life but I think the indel rate virtually always exceeds the substitution rate.)

To understand why this matters, consider an example:

    ATG-AG
    ATGT-G

This is an 'impossible alignment' under the probabilities you gave since here we have a transition from a gap-residue alignment to a residue-gap.

However, under our assumption that mismatches are more likely biologically than indels, the correct alignment should be:

    ATGAG
    ATGTG

Indeed, the latter does look like a better alignment.

This also follows for more complex examples, so this:

    ATG--AAG
    ATGTT-AG

Becomes this:

    ATG-AAG
    ATGTTAG

(Or this:

    ATGA-AG
    ATGTTAG

)