According to the rules,
The process of becoming a lich is unspeakably evil and can be undertaken only by a willing character.
What if a lich, having done this, slowly over time realizes its ways were wrong? Do the rules
Yes...depending
Alignment causes a lot of arguments around the D&D community. There are a pair of rock-solid methods: the Sanctify the Wicked spell, and the redemption rules, both of them found in the Book of Exalted Deeds. The BoED can be a controversial book in some groups, but those rules are a definite method of getting the lich back on the straight and narrow.
And then we get to the less-clear part.
D&D's alignment system can be inconsistent at times. Some sources say alignment is about action; other sources imply that it's about the intent behind an action. There's elements of belief systems and thought patterns in alignment too, which complicates the matter further. The Player's Handbook says alignment is supposed to be a guide; other sources treat it like a straightjacket. All of this makes the question, "Could this lich seek redemption on his own?" extremely difficult to answer.
I am inclined to say yes, no being is past redemption. The idea that any being with free will, down to the most vile and wretched demons, can find redemption is the cornerstone of how the Good alignment treats others. Celestials and fiends are polarized by these opposite beliefs - that any being is capable of redemption (even if it's not) in the case of celestials, and that no being is above corruption (even if it is) in the case of fiends. While an argument could theoretically be made that fiends are past redemption (an argument that's riddled with holes - there are canonical examples of non-evil fiends), the lich you're discussing is a mortal, born, living, and now undead with full control of their own free will. If they have a reason to turn from evil - even if that reason is weariness, or a craving for acceptance - then I don't see a reason that they can't, especially if it makes a good story.
As for true death, there's a few avenues for that - the easiest is for the lich to smash his phylactery, then kill himself. However, there is another option - regaining mortality. Resurrection and True Resurrection can both return an undead being to true life, and by RAW you don't even need to break the phylactery. The lich would be mortal once again, but would be able to live out the rest of their natural years and then die in peace.
As to the greater question of if their act of unspeakable evil to become a lich can be forgiven...in the spiritual sense, the Book of Exalted Deeds states that no being is beyond forgiveness if they truly seek to repent - at least, not in the eyes of the forces of planar Good and the gods of that alignment. Forgiveness from the lich's victims is another matter entirely.
A Note for Pathfinder Games
Pathfinder's alignment system is essentially just 3.5s; however, the developer's attitude towards it tends to be more consistent. Sean K. Reynolds, Jason Buhlman and the various Pathfinder writers gleefully embrace fantasy racism and the idea that a being or being(s) can be born irredeemably evil. That doesn't have to affect how you run your game, but tread lightly in Pathfinder Soceity games.
Okay, let's take a look.
Without any rules in front of me, I would say that two things would stand in the way: first, only a creature that recognizes the error of its ways can truly seek redemption (you've mentioned this), and second, the magics involved in "ascension" to lichhood are very powerful, very evil, and most likely very capable of warping an already malignant and corrupt soul beyond the point of recognition.
That said, the multiverse is a very large place, and the eternity of a lich's undead existence is a very long time. Were a lich to somehow change its tune, the ruling at my table would be that the only feasible means of its redemption would be through death (and the willing destruction of its own phylactery), or possibly (POSSIBLY) through magic that is as powerfully good-aligned as the lich creation rites are powerfully evil-aligned.
Beyond rules, the reason(s) why a lich seeks redemption might be argued.
A lich is an undead spellcaster, usually a wizard or sorcerer but sometimes a cleric or other spellcaster, who has used its magical powers to unnaturally extend its life
According to D&D 3.5, a lich either can be arcane or divine.
A cleric who devoted his life for his deity and his cause. If it was an evil deity and becoming a lich might be a purpose for him (any follower of Chemosh, the god of undead might be an example of this). In that scenario, redemption could not be a choice at all.
For a cleric of non-evil alignment, the character probably will commit great sins for his deity and his religion while becoming a lich. In that point, the character might need an atonement with a great quest to accomplish for his deity. That must not be easy as it sounds.
For arcane casters, situation gets complicated, since lich looks like a way to extend lifespan and get some extra abilities and powers, unless the character is heading for demilich. So, process and reason to become a lich is a way for greater power and life span.
A character dedicated his life for power and his magic and do not care the rest becomes evil (unless he is already evil) with thirst of power and domination and walks the paths of becoming a lich. He already knows the cost and makes himself ready for all! After becoming a lich and gaining a great lifespan and greater powers, it was hard to give away all these and quit the chance of gaining much greater power (becoming a demilich).
So, according to that point, a character who becomes a lich probably will not seek redemption. If he does, then he must have good reasons for that.
In the situation of a previously non-evil cleric who became a lich, a great quest must be asked for his redemption, the reward (a restful death or a total redemption) might change according to deity and the quest accomplished, but that must be far beyond than taking another template.
In the situation for a arcane caster, I do not see any reason to turn back, especially after all those efforts and all these gains, adding the possibility for gaining greater power, an arcane caster would not turn back. But if he really wish for another chance, then I said NO! You must not started to walk in the dark path of becoming a lich and it is too late to turn back.
UPDATE: Well, in fact, it is a strict answer, I know. and I realize it is not complete.
In my games, role-playing is important and becoming a lich is not simply spending some gold, creating a phylactery and taking a template. Player must role-play and prove me that he really wants to become a lich. And my answer is what he will hear during that process. Also when he want to turn back, he will keep hearing that.
But in fact, it is all about role-play and if he keeps trying to find a way, then he might find a way. He must convince the gods (or the great power that can help him) in the process, so he must convince me for that. And it all about what he did and what sacrifices he accepted and what sins he commit.
If he finds a way to make amends for all he had done, then he will be redeemed.
But again, as a DM, do not tell this to your players or how they could redeem themselves. It must be something they must find out.
It's funny that you mention Forgotten Realms, because its lore on liches is rather different from the core rules.
What you're talking about sounds kind of like what FR calls an archlich. As far as I'm aware, the only 3.x book that talks much about them is Monsters of Faerun, which is 3.0 (it predates the actual release of FR3e, and doesn't even reflect the metaplot updates in that book). Some archliches have the transformation forced on them, while a rare few are good characters that became liches for their own reasons. Neither of these should be possible by the core rules, but in FR they are. Archliches have a slightly different power set from standard liches, but it's not just a matter of flipping everything around to "good-flavored" versions: these are still recognizable as liches, even if they work a little differently.
That said, your description also differs from this lore in one very big way: MoF speaks of good characters becoming liches, but you're talking about a lich becoming a good character. What I've described above is only what a good lich might look like: I know of no rules to adjudicate your path to getting there. But it could make for a very interesting plot hook.
As others have said, we're talking about someone who became evil enough to consider the lich transformation a viable option. What could even make someone like that want to change? I'd argue that it can't be done, but that's not to say that it couldn't happen in your campaign, or even one of mine: only that the story should involve people doing things that can't be done. In other words, this is the sort of thing legends (and the final adventures of entire campaigns) are made of. If you want your "redeemed lich" to be believable, then you're going to need to know its legend, and it really needs to be something legendary.
