I arrived home from work, and passing by the Shul near my house noticed they were davening Mincha, so I went in and joined in. Just after starting Shmona Esrei I remembered I had already davened Mincha with a minyan earlier in the day, so I stopped and left. Was I correct, and if not what should I have done?
Yes. What you did was correct. One who begins praying Shmoneh Esreh thinking that he has not yet prayed it and then remembers that he had already prayed, must stop even if he is in the middle of a blessing. The Mishnah Berurah explains that since the beginning of his prayer was for the sake of an obligation he cannot finish it as a voluntary prayer. An offering cannot be brought partially as an obligation and partially as a voluntary offering. (Shulchan Aruch Orach Chaim 107, 1, & Mishnah Berurah 7. Sefer Shegiot Mi Yavin 11, 88 & note 139).