In Season 5 Episode 2, Double Date, of "How I Met Your Mother", they discover a doppelganger of Lily as a stripper. Narrator Ted mentions that it was the third doppelganger, and then shows clips of a doppelganger for Robin and Marshall. But I don't remember those episodes. Were they actually part of an episode?
I believe the Dopplegangers first came up in Season 5 only.
The excert from Wikia also confirms this:
The first doppelgänger shown is Robin's doppelgänger, dubbed "Lesbian Robin" by the group. It is unknown when exactly she was first seen; in Double Date, Future Ted tells his children how earlier he and the group, while walking through New York City, came across a woman who looked exactly like Robin, and due to her appearance named the doppelgänger "Lesbian Robin".
The second doppelgänger is Marshall's doppelgänger, dubbed "Moustache Marshall" by the group. It is unknown when exactly he was first seen; in Double Date, Future Ted tells his children how earlier he and the group came across an advertisement on the back of a bus with a photo of a man who looked exactly like Marshall, and due to his prominent moustache they named the doppelgänger "Moustache Marshall".