The answer is straightforward, but it is worthwhile to analyze the rationale.
The gemara[1] states: “Rav Yehuda said in the name of Shmuel: If one was standing in prayer (i.e., in the midst of Shemoneh Esrei) and remembered that he had already davened, he should stop, even in the middle of a beracha.” Thus, it appears that when you became aware of your predicament, you should have stopped immediately.[2]
The question is how one reconciles this ruling with what follows logically from the previous segment of the gemara. Specifically, R. Elazar says that one who is not sure if he davened should not daven out of doubt. However, R. Yochanan, whose position is accepted as halacha,[3] argues, saying: “If only a person would daven all day long!” Considering the fact that one does not recite berachot when he is unsure of whether they are called for, R. Yochanan’s language implies that it is not a problem for someone to daven even if he did daven previously. Why, then, is your case different?
Further confusion arises from a subsequent gemara, which states that one who already davened and enters a shul in which people are presently davening may join them as long as he adds something new to Shemoneh Esrei (i.e., during the middle thirteen berachot, which consist of requests[4]). Accordingly, why doesn’t the gemara instruct the person in the situation that you describe to simply continue by adding something to his prayer?
The Rosh[5] reconciles matters. He submits that R. Yochanan did not mean that one may literally daven all day long without any further conditions. Rather, one may daven an additional time if he adds something new to the Shemoneh Esrei. The rationale is that one may daven a second time only as an optional tefilla (nedava), which he undertakes in order to add something that was not included in the first one. If he does no more than repeat, it is deemed to be a second mandatory Shemoneh Esrei. Since tefilla corresponds to the korban tamid,[6] which is brought only once during a given time period, one must not daven two of the same tefilla. Only if he davens in a manner that shows that it is a nedava is it permissible, as an individual can offer an optional korban olah[7] in a way similar to the korban tamid. The congregation, on the other hand, may not repeat Shemoneh Esrei, because an optional communal olah was not permitted in the Beit HaMikdash. Similarly, one cannot daven an extra Musaf, just as an individual could not bring a korban parallel to any of the Musaf offerings in the Beit HaMikdash.
One who is unsure whether he had davened is obligated to recite Shemoneh Esrei and need not add anything to the tefilla because the prospect that he may actually need this tefilla is equivalent to adding something new.[8] However, one should mitigate the possibility of a superfluous Shemoneh Esrei by making the following conditional statement:[9] “If I did not daven, this should be an obligatory tefilla. If I already davened, it should be deemed optional.”[10]
If one starts Shemoneh Esrei thinking it is a normal, obligatory tefilla and realizes in the middle that he had already davened, he is stuck. The tefilla cannot be reclassified at this point as a nedava, and there is therefore no framework with which to continue, even if he wants to add something.[11] Only if one began with a doubt and a condition that envisioned nedava from the outset can he continue after realizing that he had already davened.[12]
In the case of one who remembered in the middle of Shemoneh Esrei of Ma’ariv, which always has an element of nedava,[13] there are poskim (especially Sephardi)[14] who say that he can then continue to daven as a nedava, as long as he adds something new. However, the Magen Avraham[15] and Mishna Berura[16] maintain that since Ma’ariv is treated nowadays as an obligatory tefilla, it is no different from other tefillot.