Currently we force users to set Visibility = "Public User Pages and Listings" if they want a field to be "Searchable" (i.e. part of a profile search form). This is an arbitrary restriction. We should allow Searchable for either Public User Pages OR Public User Pages and LIstings.
NOTE: Just removing the formRule in CRM/UF/Form/Field.php does NOT fix this - you can save the field w/ Public User Pages visibility but it doesn't show up in the search form fieldset.