Hey there,

The reason they will get this message is because you had set 'Who can view my profile page' to 'My Friends', so when users search someone who is not friend with will not able to view his/her profile.

If you want registered users are able to view someone's profile who is not friend with, you can set it to 'Registered User' from your Profile Type under Privacy Tab. (Kindly refer the screenshot)