(Not an evolutionary biologist, but I couldn't resist :)
I don't think your premise is correct. In (symmetric) cell division, we should consider that the old cell "disappears" and two new cells appear; neither of the two daughter cells is the parent cell, they are both descendants of it (hence the term "daughter cells"). The parent cell is gone. Therefore, at least for symmetric cell division, the lifetime of a cell equals the length of a cell cycle. So cells are not immortal --- only the cell lineage is.
Asymmetric cell division (as in stem cell division, not budding) is more tricky. Here it might seem as if there really is an immortal cell (the "stem cell") generating "mortal" offspring. But I think the situation is really the same as in symmetric cell division: most of the cell cycle mechanisms are identical, and again two new daughter cells are generated, and the parent cells disappears. The asymmetric part is that only one of the two daughter cells are "permitted" to continue the line. Again, the cell line is immortal, the cell is not.
But this is still true in higher organisms: the germline is an immortal line, while the somatic cells are not. So the key difference between higher organisms that have a clear life span and unicellular organisms is the appearance of cells that do not generate offspring, but instead support the cells that do.
I'm not sure there is a sharp transition from single cells to the germline/somatic cell situation. Intermediate cases are found in all sorts of single-celled organisms where certain cells "decide" that it's better to support their (genetically identical) neighbor in some way to rather than divide themselves; these are a form of "somatic" cells. All sorts of community behavior in bacteria and other microorganisms could be viewed in this way. During evolution this behavior has gradually got encoded into the DNA itself, with more and more sophisticated "support systems". Higher animals are really just the latest version of this, where the entire body is really just a support system to ensure survival of the germline.
I would suggest reading Richard Dawkin's books on this subject, especially The selfish gene. They are well written and quite accessible.