I set my profile to private. I turned off "Public Search Results" and "Facebook Search Results" is set to "Only Friends".
If you're not logged in, my URL returns a 404: http://www.facebook.com/davetufts (or by ID: http://www.facebook.com/profile.php?id=603069147 )
Not a huge deal, because the graph page only shows my name and ID, but they are publicly accessible: http://graph.facebook.com/davetufts or http://graph.facebook.com/603069147