As for a lich hiding his phylactery, the dumbest thing I've ever heard is the standard 3.0e MM's "wear it on your forehead" idea. You're a genius spellcaster with all the time in the world, a fortune, and untold knowledge both arcane and mundane, and you're wearing the secret of your eternal unlife that will make you immortal unless it's destroyed on your forehead?
Now, in 2e, I believe the rule was that if a Lich dies on another plane of existence than it's phylactery, it's dead forever, however I don't see mention of that in 3e.
If you're DM isn't using that old one as a holdover rule, then you could go and cast Genesis/Demiplane Seed/Appropriate Epic Spell and make your own demiplane to store your phylactery (Genesis may only be a cleric spell by the SRD, but creating your own demiplane by that spell or similar effect is a common wizard/arcane thing throughout D&D). Appropriate teleport shielding and anti-divination effects can should ward the entire demiplane off except for a single portal in-out (which goes into a hidden room in the cellar of a tavern you own (through fronts and minions) in a town near your lair). You then spend time with Wall of Iron and Wall of Stone building a devilishly complicated maze (which you know the only route through by heart), laden with powerful magical traps, Symbols of all types, permanent confusion effects, and at least one gateway that appears to lead to the phylactery (through illusion effects), but is actually a one-way portal to the Negative Energy Plane (a nice adventurer-disposal.) The phylactery itself is hidden in a hollowed-out stone in one wall in a dead-end part of the maze with a backup spellbook or two to regain your spells after reforming. Every decade or two, make additional decoy demiplanes that are nothing but death-traps to do-gooding adventurers who want to find your phylactery.
If your DM is requiring the Phylactery to stay on the same plane of existence as the Lich, then time for a geography lesson. Go to the arctic/antartic regions of your world, and find a mountain near a glacier or other major body of water (take advantage of your immunity to cold). Find a large boulder in that area, and with creative use of Stone Shape, hollow out a small room inside (and seal it off once it's created, so there is no sign of anything out of the ordinary later). Stock said room with Phylactery, spellbooks and other items you'll need when you repop. Appropriately ward against divinations, and if possible, against incoming teleportation without a proper key or password (those who try and teleport in without an appropriate token to allow passage find themselves shunted to the mouth of a volcano, or the depths of an oceanic trench or other bad place). Then, take this hideaway and plunge it into the deepest, coldest, darkest part of the arctic waters. You can't drown and you're immune to cold, so find an appropriate crevice, trench, or undersea cave to hide this boulder in. If neccesary, use Transmute Rock to Mud and on the surrounding rocks to seal it in, making it look like a natural part of the environment.
