The phylactery is in his ribcage. Over the years, he's had so many nondetection and false aura spells cast on him that it's impossible to distinguish the aura of the phylactery from his own aura. Casting "Wish" just brings the lich to the characters (Tell the players: "It seems that that the lich and his phylactery are so magically similar that wish just brings the closest one to you.") Killing the lich just causes him to re-form right where he was; in fact, he tells the characters about this from the start, using this fact as 'proof' that he can't find his own phylactery (perhaps going so far as to kill himself right in front of the characters, and then innocently saying, "I don't know why I didn't reform at my phylactery!")
Combine this with several really good fake phylacteries. Each time the players destroy one, they return to the lich who says, "Sorry, my phylactery must be in another castle." The lich is very, very helpful, does everything he can to seem extra nice, giving all sorts of magic items to the party, healing them when they're hurt, and genuinely hopeful that the characters will eventually manage to find him the eternal rest he so desires. He gives them clues as much as he is able to, directing them to places where the phylactery might be.
Meanwhile, the lich is actually just going about his daily life as normal, while the characters systematically destroy every other lich in the entire campaign world on his behalf. If he's smart, he's hired every powerful group of adventurers around, giving each the "please kill me" story. If the players start to distrust the lich, then they have to deal with the other adventurers who do trust him, and who have begun to see the lich as a benevolent friend.