You can search for first and last name, or you can search for somebody's e-mail address. If that person is "in your network" (reachable in the friend-graph using less than some number of hops, I presume), then you can click on the resulting links to verify you've got the right person. If they're not reachable from you, you can't click to verify, but you can blindly invite them to be your friend.

It's clunky, but that's the general idea.