From the SRD:
"The Lich’s Phylactery
An integral part of becoming a lich is creating a magic phylactery in which to store its life force. Unless the phylactery is located and destroyed, the lich reappears 1d10 days after its apparent death.
Each lich must make its own phylactery, which requires the Craft Wondrous Item feat. The character must be a sorcerer, wizard, or cleric of at least 11th level. The phylactery costs 120,000 gp and 4,800 XP to create and has a caster level equal to that of its creator at the time of creation."
So... Nope. It would seem to indicate that the Lich's body simply reforms and reanimates wherever he died (or somewhere nearby), rather than near the phylactery.
Permanently Losing the phylactery sounds like a good idea. Though, I wouldn't send it to an elemental plane... Sure, it's tough for the PCs to find, but do you really want to take the chance of some irate Djinn or Efreet stumbling across it?