Tosafos in Baba Kama 4b says that the concept of כאשר זמם ולא כאשר עשה, which means that after the person has been killed, the eidim can't become zomimin, doesn't apply to monetary cases. Tosafos offers 2 rationals for this: 1. Money can be returned so it is never too late. 2. The reason we can't be mechayev after the person has been killed by the court is אין עונשין מן הדין but by money we can learn from a kal v'chomer that after it has been paid they should certainly become zomimin. Tosafos seems to hold that it is only for monetary issues where we don't apply this concept, but by malkus we would apply this concept. Meaning, if eidim were mechayev someone malkus and he already received the lashes, they can't become zomimin.
Rambam (Hil. Eidus 20:2) disagrees with Tosafos and holds that even by malkus they can become eidim zomimin after the person they were testifying about had already received the malkus. Although the Ra'avad disagrees with the Rambam, the Kesef Mishna comes to stick up for the Rambam with 2 very interesting approaches. His first approach is that the reason we don't turn them into eidim zomimin after the person has been killed is that their crime was to severe to allow them to have a kapara by becoming zomimin. But, malkus which is not so severe, we allow them to have a kapara by becoming zomimin. His second approach is that when someone was actually killed, he must have been guilty because hashgacha wouldn't allow an innocent life to be lost, but malkus could have been given even though he didn't deserve it so they can still become zomimin. Nonetheless, these reasons aren't sufficient to explain the opinion of the Rambam, since it is not the derech of the Rambam to create distinctions in sevara that aren't muchrach in the gemara.
Rav Chaim Soloveitchik offers a brilliant approach to the Rambam. Malkus is very different than capital punishment. Malkus only has a status because he violated an issur that is mechayev him malkus, and that he received the lashes in beis din, which gives it a status of malkus. If one would receive malkus without there being an absolute chiyuv of malkus, it would not longer qualify as malkus. Therefore, if later realize that the person who received malkus didn't deserve it, it would retroactively not be considered malkus - although he was hit 39 lashes, he never received "malkus". This is not the case by the death penalty, because even if someone retroactively wouldn't have deserved the death penalty, they still received the death penalty. In a case of eidim zomimin, where their testimony is retroactively uprooted, the consequence would be that the person received malkus or mi'sah wrongfully. Regarding the mi'sah, it can't be undone retroactively, therefore based on the concept that הרגו אין נהרגין we can't punish the witnesses as eidim zomimin. But, by malkus where by uprooting their testimony the malkus would retroactively turn into ordinary lashes, it is still as if he never received malkus - so they can still become eidim zomimin.
The basic premise that malkus requires a chiyuv malkus is also found in the kuntres ha'smicha in the discussion of semicha between the maharal ben chaviv and the chachmei tzefat (include mahari bei rav). The whole incentive to restore semicha was to give malkus to those who are chayev kareis, but one of the dissenting arguments is that since there was no warning of malkus and therefore no chiyuv malkus, it doesn't qualify as malkus.
The distinction of Rav Chaim explains the fact that we find in the gemara סנהדרין לז - אע"פ שבטלה ד' מיתות, דין ד' מיתות לא בטלה - substitutions post the destruction of the beis hamikdash for capital punishment. But we don't find that one who is chayev malkus would also be punished with malkus. Perhaps the distinction is that sekila and serei'fa that would occur outside of beis din would still be considered to have the din of סקילה ושריפה, but malkus outside of beis din wouldn't have a status of malkus and therefore it wouldn't accomplish anything.