The Gemara in Berochos 26b says that if one needs to make a hashloma for a missed Shabbos Mincha through davening Motzei Shabbos Maariv twice, he should say Ata Chonanonu only in the first Shemone Esrei - to show that this tefila is meant as the current tefila, namely Maariv - and it should be omitted in the second Shemone Esrei to show that this one is meant as the hashloma. If it switched the order, then he must daven still another one to serve as the hashloma.
Questioning this the Gem. brings a beraisa, not dealing with the topic of hashloma at all, that says that if one davened Motzei Shabbos Maariv and omitted Ata Chonantanu, he is nevertheless yotzei since he will say Havdala anyway on wine. The Gem. remains with the kashya.
I don't fully understand how this last beraisa contradicts the fact that because he left out Ata Chonantonu in the 1st of the 2 Shemone Esrei's in the ''hashloma'' situation he is not yotzei. The reason he wasn't yotzei was because it was a hashloma situation and he was required to say havdala ''dafka'' in the 1st tefila. Not because the din requires havdala always recited in the tefila. In the later beraisa, it is speaking of a general rule in regard to saying Maariv Motzei Shabbos without any connection to the inyan of hashloma, and he simply doesn't have to daven again since he will accomplish Havdala over a cup of wine.
Although the Gemara did not accept your reasoning,and did not feel that the fact that one remembered Havdalah in the second Shemonah Esrei proves that it is the Chovah, Rav Hai Ga'on (quoted in Rosh) did. He says that since the Gemara says "Kashya" and not "Teyuvta" we may accept the ruling of the first Beraisa, using the reasoning you offered.
Why does the gemara wonder if one missed mincha may he daven maariv twice? By korban Tomid of the morning one can not make it up by mincha yet one can daven two minchas if he missed shacharis. so of course the same should apply to missing mincha.
In other words, we know that tefillos don't have the problem of ovor yomo batel korbono simply from the fact that there is tashlumin for missing shacharis and marriv so why should mincha be any different?
Although the Tefilos were established to correspond to the Korbenos Temidim, there is also a separate Takanah that one is obligated to Daven three Tefilos each day. Although they are limited to certain times, still the Takanah is that one must Daven three Tefilos.
Therefore, with regard to Ma'ariv, there is a consideration that Ma'ariv -- which is the next day -- cannot be Tashlumin for Minchah of the previous day.