After Voldemort fails to kill Harry when Harry is a baby, the Avada Kedavra Curse rendered him a spectre-like being.
In Goblet of Fire, Voldemort says:
I was less than spirit, less than the meanest ghost ... but still, I was alive. What I was, even I do not know ... I, who have gone further than anybody along the path that leads to immortality. You know my goal – to conquer death. And now, I was tested, and it appeared that one or more of my experiments had worked ... for I had not been killed, though the curse should have done it.
Goblet of Fire - page 566 - Bloomsbury - chapter thirty-three, The Death Eaters - Voldemort
‘There was no hope of stealing the Philosopher’s Stone any more, for I knew that Dumbledore would have seen to it that it was destroyed. But I was willing to embrace mortal life again, before chasing immortal. I set my sights lower ... I would settle for my old body back again, and my old strength.
Goblet of Fire - page 569 - Bloomsbury - chapter thirty-three, The Death Eaters - Voldemort
Voldemort says he was willing to embrace mortal life again before chasing immortality.
Does this mean that when Voldemort was in his spectre-like, less-than-a-ghost state, the Horcruxes were somehow not keeping him immortal? Voldemort himself describes himself as being in a state where he had to embrace mortality again before pursuing immortality. What does this mean?
ETA: To clarify, a different way to ask this question is: How could Voldemort have "embraced a mortal life" while he had Horcruxes -- didn't the Horcruxes make him immortal?
I really have no opinion one way or the other -- I'd like to consider all interpretations (please keep them based in canon.)