Searchable user profiles

I’m after the ability to do the following, I’ve searched for a plugin (whether an off-the-shelf, or one I can manipulate for my needs), with no luck:

1. There will be 2 catalogs. One will display individual records/details (name, position, skill set), the other will be company listings.
2. The data will be displayed in a page.
3. Each catalog will be searchable by criteria (type/skill set/sector).
4. A user can update their own post/page/listing (essentially it’s each user’s profile page).

My initial thinking is, use advanced custom fields, and allow each user to create a post, where they can type their details. The problem I see is, how can they be searchable by criteria, and how can they only post one (instead of multiple by mistake)?

The purpose of the listings are ‘member’ details to a club. The users will display their details to all other members, and be searchable for specific roles/jobs. While the company listings (sponsors) will display their contact details, and short description.