Yeah, what the others said. You can set certain info on your Lodestone page to private, but you can't hide the page itsself.
If you can't find them at all, make sure to include all languages, classes, servers and so on in your search. It also helps to search for just the first or last name instead of both together.
If all else fails, google "firstname lastname ffxiv" and they should be the top result.

Another possibilty is that they just went through a name change yesterday. The Lodestone is kinda slow in catching up, when I changed my name it took a while until I could be found there with my new name.