Throughout all of the Star Trek shows, one of the constants is the appearance of new life and new civilizations. However, it is pretty rare for that new life to appear after their first appearance. The only example that was encountered again that I can think of off the top of my head is the Borg. What other first contact species have reappeared in any of the Star Trek shows?
This happened several times. Off the top of my head I thought of the following examples:
The Founders and The Dominion
Of course Odo and other shapeshifters had lived within the Federation for years before the events of DS9, but it wasn't until 2371 (DS9: The Search) that official first contact occurred when Odo discovered his home planet. After that The Founders made frequent appearances. Later episodes of DS9 also described the actual "first contact" with Odo by Bajorans. Official first contact with The Dominion would be either in 2370 when the Ferengi traveled to the gamma quadrant to trade with them, or when the Jem'Hadar traveled through the wormhole and began attacking Federation colonies shortly thereafter.
Voyager discovered this fluidic-space species in 2373 during the events of Scorpion when they tried to invade normal space. Two years later they encountered Voyager again and ended hostilities.
We don't know what species he is, but Starfleet had made contact with him by at least 2360, and he was first shown in "Where No One Has Gone Before". He went on to meet the Enterprise crew two more times after that.
The first contact with Q, or The Q, made contact with The Federation in the first episode of TNG - "Encounter at Farpoint." It's possible that Trelane, encountered in 2267 was of the same species. Q appeared numerous times again in TNG, DS9 and Voyager.
The Federation knew of the Ferengi, but made first official contact with them in the TNG episode "The Last Outpost". (hat tip to J Doe for the reminder) They "unofficially" made first contact with Humans in 1947, but those records were lost.
The Crystalline Entity
Probably not what you had in mind, but first contact with the Vulcans was shown in First Contact, and they appeared continuously throughout the series. (both chronologically and in subsequent productions)
Again, this was already an established species, but first contact was shown in the first episode of Enterprise, Broken Bow.
I'm sure there are some more examples. It was pointed out in the comments that Voyager encountered quite a few species in the Delta quadrant that re-appeared in multiple episodes. Considering Voyager to be Starfleet's unofficial emissary to the Delta quadrant, these would count as "first contact" too.