Here's a simple option, especially if you want to require the lich to remain within a certain range of his phylactery, have to have periodic physical contact with it, etc.
Pick one random stone out of all of the stone walls in the lich's lair. Have it be of sufficient size that only a spellcaster as strong as the lich can Reduce it (reverse of Enlarge spell). Have a small cavity hidden behind the stone, just large enough to accommodate the phylactery, and make sure the stone is thick enough that Detect Magic and other divinatory spells are blocked. Add more powerful obscurements as you feel necessary.
The players will have no reason to look behind that particular stone to find the phylactery. Even if they manage to come up with some way of locating it, now they need a spellcaster powerful enough to shrink a stone of that size -- in other words, a spellcaster as strong as the lich himself.
Oh, and be sure to add extra layers so that a simple Transmute Rock To Mud won't be enough, and maybe put in a booby-trap or two as well. I mean, the lich has presumably had centuries to come up with ways to protect his phylactery.