OK I got a strange scenario. I created a field on a custom record as an Admin, and now other Admins can see that field on the custom record, but they can't search it. No restriction on permissions.