In the Braisa quoted by the gemara, R. Akiva holds that there is malkus for those who deserve kareis, but no malkus for those who deserve capital punishment. The Braisa (according to Ravina at the end of the page) explains the rationale is that teshuva works to achieve atonement in shamayim and therefore works to exempt from kareis, but doesn't work to exempt from the death penalty in beis din. Therefore, the pasuk which says כדי רשעתו- משום רשעה אחת אתה מחייבו, only prevents malkus for capital sins because the death penalty is inevitable, but wouldn't apply to kareis since teshuva can exonerate him from kareis.
The Noda B'Yehuda (kamma, o.c. 135) raises an interesting question. Why doesn't teshuva work to exempt from mi'sas beis din (capital punishment)? One possibility is that beis din doesn't recognize teshuva because that is purely between man and G-d. But, this is inaccurate. Beis Din certainly recognizes teshuva and acts based on it. If one became passul l'eidus, beis din can restore his believability as a witness after they are convinced that he did an adequate teshuva. So why can't they exempt from misah after he does teshuva? Another suggestion could be that Beis Din can't delay his judgement because he MAY do teshuva, so there is no case where he would ever have the ability to do teshuva before being killed. This is also not true. If one violated shabbos then spent the next 5 years doing serious teshuva, even if the witnesses show up in court at the end of 5 years, he would be convicted and killed. Why? The Noda B'Yehuda explains that had the essence of teshuva been torture and suffering, we would have had a tradition teaching us the precise amount of suffering needed for atonement on each aveira, and beis din would have exonerated the criminal after assessing that he did an adequate teshuva. However, the essence of teshuva is in the heart and can be fulfilled in a רגע כמימריה - in an instant. Therefore, if teshuva would help to exempt from capital punishment, the beis din would NEVER be able to carry out capital punishment because there is always the possibility that the person did teshuva. The very fact that the Torah demands capital punishment for certain aveiros forces us to say that there is no possible repentance to acquit from capital punishment. The rationale would be that the Torah wants the death penalty to be a deterrent from the aveira, and would only work as a deterrent if there is no way out.
However, anything which is dependent on Hashem such as kareis, teshuva would certainly work for. The Maharal Ben Chaviv (kunteros HaSemicha) explains that even when the mishna says that malkus helps to exempt from kareis, it really means in conjunction with teshuva. Malkus alone without teshuva would not exempt from kareis. Teshuva alone without malkus would lessen the severity of the karies, but teshuva together with malkus would remove it entirely.
On the side of the shulchan aruch in hilchos aveilus there is a commentary called "milu'im" (not printed in all versions). In Y.D. 340 he elaborates to explain the opinion of the Rambam (Hil. Avoda Zara 4:6) who seems to hold that even after an entire city does avoda zara with warning and witnesses, they have the ability to do teshuva and be exonerated from being killed as an Ir HaNidachas. This Rambam is very difficult because it seems to contradict the premise of R. Akiva that teshuva doesn't remove capital punishment? The Mi'luim explains that although teshuva doesn't exonerate for capital punishment which is meant to serve as a deterrent, it works for an ir hanidachas. The killing out of the Ir HaNidachas is not to serve as a deterrent to other cities (it doesn't say by ir hanidacha - והנשארים ישמעו ויראו or ובערת הרע מישראל which are pesukim that indicate the purpose is to deter others from following suit), rather it is a direct punishment that the city deserves for their public and communal violation of aveirah. Teshuva works for any time of punishment that is not meant to serve as a deterrent and therefore works even for an ir hanidachas.