In Star Trek: First Contact, I know that we learn that Vulcans were the first extra-terrestrial species discovered by humans (or, more correctly, humans were discovered by Vulcans) and I know they have a sort of telepathic ability, but what were the first pure telepathic species encountered (by pure, I mean they solely communicated through telepathy)?
As far as I can tell, the first wholly telepathic humanoid we see in any of the Trek shows is the Cairn. The main thrust of the episode TNG: Dark Page is about Lwaxana Troi attempting to teach them to speak rather than simply using their minds.
That said, Kirk encounters any number of species that are telepathic but most of them are simply presented as monsters.
There are many beings in the Star Trek Universe that use telepathy, now the first ones that I can remember that I don't see using verbal communication would be the Melkots. Although Richard is correct about Cairns losing their ability to communicate verbally and teaching people how to communicate telepathically, the Melkots were introduced in the Kirk Era.
The Melkot (or Melkotians) were a telepathic and xenophobic civilization from the Alpha Quadrant. The Melkot used their telepathic powers to punish aliens who encroached upon their space without permission (which, prior to 2268, they never extended).
The Federation made First Contact with the Melkotians in 2268, when the USS Enterprise encountered an orbiting warning buoy. When Enterprise Captain James T. Kirk ignored the Melkot warning to leave their territory and instead, assumed orbit and beamed down a landing party, the Melkotians passed harsh judgment on the landing party, describing them as "aliens" and "disease" and condemning them to death for their trespass.