Well, the two interfering amplitude diagrams do not quite cancel each other out: they almost cancel each other out. That is to say in the notional limit that the mass of the u and the mass of the c were identical, the two diagrams would be identical except for the minus sign of the Cabbibo (CKM for 3 generations) matrix influence on the vertices, which you reassure us you are comfortable with.
To the extent the masses of the two quarks in the internal lines differ, the effect of them on the respective propagators differ, and so the respective results of the loops differ. In fact, good SM books compute the nonvanishing, but vastly suppressed amplitude. It is a function of $m_c/m_u$ which goes to 0 as that ratio goes to 1. Something like $\propto g^4 \frac{m_c^2}{M_W^2} ( 1-m_u^2/m_c^2)$.
So you might sensibly object that the term in the parenthesis is much closer to 1 than it is to 0. But, look at the factor multiplying it, $\alpha^2 m_c^2/M_W^2$, and how small it is: do this. (Still, if that were a part of your puzzlement, perversely, the introduction of c actually increases the $\Delta S=1$ rate instead of suppressing it! Historically, the rate was used to bound the mass of the then hypothetical c from above!)
When the third generation is introduced, the 3x3 unitary analog matrix (CKM) performs the same function. The quark mass ratios are bigger, but the couplings are suppressed at the vertices, so, if I recall, the effect of neglecting the 3rd generation is not dramatic.
- Extra credit hypothetical: In an imaginary world where the masses of u and c differ by one part per million, but are huge, say half the mass of the W, would you have this strangeness-changing neutral current amplitude be suppressed, or not?