Trap the soul: Yeah, it'll work fine. You don't even have to kill the lich first--just cast it, or if you're feeling clever trick the lich into picking up the thing.
Create soul gem: Nope, for two reasons. First, it's a death effect, and undead are immune to those. Second, it only works on creatures who are dying or died in the last round. Liches, animate or otherwise, are dead and in most encounters have been so for more than a round.
It's not really about preventing reconstitution. Trap the soul doesn't kill or destroy a creature, and it doesn't do anything to souls that aren't currently creatures. It takes a creature, body and soul, and puts it into a gem. There's nothing about vampires, liches, or even soulless constructs that make them any different than Joe Commoner when it comes to trap the soul.
Like Blahpers says, trap the soul should work fine on any creature as long as it has the soul. So in the case of an undead, it should work as long as the creature has a soul/'life force' (we can probably use magic jar's wording to help in which case we can assume that (intelligent) undead have or are life forces, just negative life forces.
Unfortunately, in the case of liches, the wording on liches' phylacteries could be clearer on what it does (or maybe the writer thought it was clear enough). It merely says it is created to store a lich's soul. This is not clear on whether that means that the lich's soul is placed into it and the body goes on about its business or whether the lich makes a box and when it's destroyed the soul goes into the phylactery and rebuilds.
Personally, the way I read it, the lich's soul is stored in the box, but that's just me. That would mean that the lich would be immune to things like trap the soul and other such spells (like magic jar) unless used specifically in the range of the soul in the phylactery or on it.
However, it does appears that in 2nd edition, they have made a Lich's Phylactery equipment item, and that wording specifically says that when a lich is destroyed, its soul flees to the phylactery. That makes such adjudication much clearer, but that is most certainly not the case in 1st edition. That item is vastly different in durability, cost, and power from a 1st edition one.
So it really depends on how your GM views a lich's phylactery and whether the creature's soul/life force is technically present at the body (where your soul trapping spell is assumed to be taking place.)
The description of the lich specifies that the phylactery contains the soul of the lich. The process involves the extraction of the spellcaster's life-force and its imprisonment in a specially prepared phylactery. Using the word imprisonment makes it pretty clear that the soul of a lich is permanently contained in the phylactery, not just when the body has been destroyed.
Since the lich’s soul is separate from his body the lich is not affected by trap the soul. The target of Trap the Soul is one creature, not one creature and an object. Since the lich’s phylactery is an object not a creature it is also not a valid target for the spell.
Funny thing. Rename trap the soul to put creature into a gem and reread the spell description and properties. As far as I can tell, nothing in the description requires the target to have a soul at all, much less have it be part of the physical creature being targeted--everything that affects the "life force" also affects the material body. It should work fine on pretty much anything, including soulless constructs.
Actually the description of the lich and the spell both use the words life force. The bolded part of my previous post was taken from the description of the lich. Below is the relevant section from the spell.
Trap the soul forces a creature's life force (and its material body) into a gem.
The spell also uses the word and, not or in regards to the material body. This means that for the spell to work it has to target one creature and affect both its life force and material body. Since a lich does not have its life force in its material body it is not a legitimate target for Trap the soul.
Whether Trap the soul works on a soulless creature is irreverent to it working on a lich. Although I would suggest that the very name of the spell suggests it does not, but like I said that is another argument.