From memory, Voldemort's pet snake doesn't make an appearance in the Harry Potter series until book 4, Goblet of Fire. When Nagini attacks Mr. Weasley, nobody really makes the connection between a giant snake and Voldemort. This implies that Voldemort didn't have Nagini when he was powerful the first time. I've also been told that there were only ever 6 Horcruxes at one time, implying Nagini wasn't made a Horcrux till after the Diary was destroyed in Chamber of Secrets. Did Voldemort get Nagini in Albania while in hiding? If so, from where? Giant snakes aren't exactly native to the country. Where did Nagini come from?
Before Voldemort's second exile he had no need of a snake to do his bidding. He was powerful enough and had enough Death Eaters.
Subsequent to becoming no more than a wraith at the end of the first Wizarding War he no longer had the strength for most magic, and fled to Albania1. Whilst in Albania he possessed snakes to keep himself mobile2. This is the first time we hear about him interacting with wildlife in his 'altered state'.
It was here he met Quirrel and they made a merry jaunt back to Britain. However his plans failed in the first book, and he then returned to Albania2 where he stayed after 1992 until around about 1994 (second exile).
My conjecture relies on this fact, that he met Nagini in Albania either in the the first or second exile but was unable to either horcrux her in the first exile, take her with him or simply hadn't met her. There's no hard evidence but from what I remember, both times he goes directly to Albania implying there is nowhere else he could have found the snake.
1.Harry Potter and the Philosopher's Stone
2. Harry Potter and the Goblet of Fire
It is even possible for Nagini to have originated back in the orphanage. He mentions being able to talk to snakes when Dumbledore tells Tom Riddle he is a wizard. Since Voldemort has a strong feeling of connection to his heritage, it would seem likely to me that Nagini was once a snake he used to talk to. The average lifespan of a snake is 10 years, and Tom Riddle constantly spent summers at his old orphanage. Having learned enough magic and passing the adult age for wizards during Winter Break (Dec 31), he could have easily magicked the snake into the massive snake we see today. It fits his psychological profile, and really only explains the deep "love" he had for Nagini. The only childhood friend of Tom Riddle.
But more conjecture I have is that Nagini existed prior to the first fall of Voledmort. Albus Dumbledore cites in one of the later books that Volemort spent his 'second life' searching for the weapon to destroy Dumbledore and to scheme. This last bit of information is mostly formed on the basis of Voldemort spending the first 4 books constantly trying to get back to life, then the 5th infiltrating the Ministry, the 6th taking down Dumbledore and securing his rule, and 7th looking for the ultimate weapon. Voldemort isn't very fluid in his plans, as it seems to be the exact same plan he had before. Nagini would have been the perfect assassin, like when she wore the bones of Bathilda Bagshot.