Starting point for the search would be the will. Any competent attorney will put down something along the lines of "To my friend, John Doe, of Eastwick, AZ, I leave ... " Notice an attorney wants to get in the relationship, the name, and a reasonable geographic location. This gives me a start when this situation arises, and if a client doesn't know where someone lives, then there's another way of setting this up that will make more sense. And it narrows down who shows up for collecting the money.
Okay, person dies and we can't find John Doe. Let's say the will is twenty years old and John Doe doesn't respond when a letter is sent to him. Now the first question is how much of an heir is John. You're not going to spend a whole lot for someone receiving the stuffed bass on the guy's wall.
Probably the next step would be to hire a private investigator in John Doe's town. PI would start with a records check (marriage, birth, death, voter, driving license, professional licenses, dog license, registry of deeds) and see what shakes out. If nothing, you go to the neighborhood and find the little old ladies who remember twenty years back. Also, advertisements would be taken out.
It's unlikely you won't get some leads (you've now probably spent about $10k). If you get nada, you go in front of the judge. If the bequest is big enough, he/she will authorize further investigation. But reality is if you strike out in the first town, you're probably not going to be successful. Reality is not all people can be found, nor can all found people (or bodies) be identified.
Best of luck,
Jim Clark-Dawe