I've seen fairies in random places, but some of them don't replenish after getting them? Where are the places I can find fairies repeatedly?
There is a spot right outside the Fire Sanctuary, in the caves with the frog mouths, with a burrowing hole. It's a convenient spot since you can come from the sky and drop in to the bird statue nearby. When you burrow in that hole and come out the other side, there is a cave with a heart piece and a bunch of fairies flying around. However, you need the Mogma Mitts in order to burrow into a hole. But you can keep going back there over and over after you get the heart piece to get more fairies.
Places where fairies naturally spawn in the world will always spawn in the same area after some period of time (my theory, after defeating a dungeon). This is in the Normal Mode and in Hero Mode. Having to go back to these locations to get them can be inconvenient so you should consider alternate ways of getting fairies.
The easiest way to get three free fairies would be to draw a Triforce on a Goddess Wall. Though you would first have to find a Goddess Wall and they can only be used every once in a while after some period of time (same theory).
A much more convenient way to get fairies IMHO would be to use Glittering Spores on regular hearts to transform them into fairies. You'll need an extra bottle to get and hold the Glittering Spores but you get five servings of the stuff when you get it giving you potentially five fairies. Hearts are much more easier to find in general so fairies will be easy to find too by extension.
Fairy in the cave you crawl into from Buccha (Kikwi Elder)'s first location (where you get the slingshot).
2 or 3 fairies in Skyview Spring, aka the last room of Skyview Temple.
Pretty sure there are fairies in the Earth Spring as well. (last room of the Earth Temple)
Lanayru Mining Facility: in the room with the sand and walls of spikes popping up as you get close, the fairy is in a jar in the corner below the staircase. (you have to pass by it to get to the staircase)
Digging spot next to the Bird Statue in the Volcano Summit. (only available after the Eldin Eruption Event)
3 fairies in the cave leading to the exterior of the Fire Sanctuary. (you have to already have the Mogma Mitts to burrow into the hole. The fairies are next to the Heart Piece).
That's all the fairies I can remember. They're only really helpful in the first half of the game, since they only heal 6 hearts.
However, since they revive you from drowning as well, unlike in previous games, it's a good idea to have some handy when swimming underwater (although an Air Potion + is better, still, but you should have at least two especially for the Flooded Faron event).