For me, Dokucraft brings back the most memories. It's the first texture pack I ever played with. I remember I had my own totally rad customized version that I picked out and everything. I used that pack for a long time before I finally started making my own.
For me that would have to be Painterly. I never used it. Never have... never will.
The reason it's nostalgic for me is that it's the first pack that I saw someone use, and it's the pack that made me conscious of what texture packs really could be. How they could change the look of Minecraft, and really make it a different experience. I first saw it when I watched Zisteau play Kaizo caverns, and later Zombie Cleo used it in her playthrough of... I think it was Legendary. The blue nether brick in Sanity is an homage to her choice of blue nether brick for the Painterly mix she used in that LP.
So Painterly is nostalgic to me because it's a substantial part of what got me making textures in the first place.
Painterly for me as well. It's the first pack that I used and I used for a long time. It also helped me to get into texture making, since I could simply modify what was in the zip, because I didn't know at the time how to extract the default texture pack from the jar.
Other than some of my old (and outright eye-butchering) packs, I would have to say Coterie Craft. I used to play with it on this one community that still brings back some great memories that I wouldn't give up for the world. Although I didn't realize it at the time, that pack gave me an insight to an art form that has brought me far and is still bringing me places. Some packs really are everything.
Painterly was my first used pack, but I don't know if nostalgic is really the correct word for it.
Dokucraft has kind of fallen from where it once stood, and it no longer gets me nostalgic.
Johnsmith has other packs made in the same style, so it never really reached nostalgia.
So I guess the most nostalgic pack for me is the Eldpack, which... still... only has a continuation. I'm not sure how well that holds up to the original, but I'll stick with it as my answer.
I'd have to say that Deep Space 1 brings back memories. It was a personal texture pack I was making for a 1.5 custom adventure map. Neither the map nor the texture pack were ever completed or released, and as to this day there is exactly one screenshot of the pack available, which I cannot find.
I didn't get Minecraft until Beta 1.8.1. Though, I was super flabbergasted with Minecraft and watch tons of Let's Plays. The mose memorable one I watched was the Yogscast, and when they used Dokucraft, I thought Minecraft itself has changed it's look. I was completely oblivious to Texture Packs at the time.