PCs are heroes. Their spells and abilities are some of things that make them heroic. Foiling those spells and powers because it makes something too easy takes them away from being heroic. However, that does not mean that we should always let PCs benefit from spells - we need to figure out whether the story makes sense for the spell or ability to work.
Is this a suitable situation where you should not have a locate object spell.... locate the object? If I were the DM, I'd check the rules, then check the story.
Rules: Describe or name an object that is familiar to you. You sense the direction to the object’s location, as long as that object is within 1,000 feet of you. If the object is in motion, you know the direction of its movement. The spell can locate a specific object known to you, as long as you have seen it up close—within 30 feet—at least once. Alternatively, the spell can locate the nearest object of a particular kind, such as a certain kind of apparel, jewelry, furniture, tool, or weapon. This spell can’t locate an object if any thickness of lead, even a thin sheet, blocks a direct path between you and the object.
This is a poorly written spell. The first sentence says it is an object that must be familiar to you, but then goes on to say it can locate a particular kind of object which implies that you do not have to be familiar with the particular item to find it, merely familiar with the type of item. There is also the nice language about blocking it with a thin layer of lead.
My interpretation of the rules is that the spell user must be *familiar* with phylacteries, in general, to try to find *a* phylactery within 1000 feet. That means they must have observed at least one phylactery within 30 feet of them, to try to find one with the spell. I would also allow a DC 20 Arcana check to replace the actual familiarity with an academic familiarity - but that is a house rule as far as I am concerned.
Then we look at story reasons and determine if the lich might predict that 'locate object' would be used and might take steps to protect the phylactery with lead (or other techniques that counter such a spell).
A lich is generally very knowledgeable, and generally focused on protecting his/her one weakness. As such, they would likely put some effort in to protect the phylactery. Would that extend to protecting against this spell? I'd roll an arcana check to see if they know about the spell (DC 12 - only a second level spell) and then, if successful, I'd allow them to have considered it in their planning. Most liches are going to automatically make this check - so most liches would take this step.
I might also have the lich consider this potential weakness as a way to trap the PCs... They might create a pseudo phylactery that can fool the spell, making the PCs think they destroyed the real phylactery, but allowing the lich to regenerate once destroyed. I also had a lich hide his phylactery within his magic staff. The PCs could not find the phylactery after they destroyed the lich, and walked off with the phylactery/staff as treasure.... which resulted in a rude awakening later on.