Plugin Advice – Membership and Database Search Combo?

I have a dilemma and not sure how to handle it, so was wondering if anyone had any advice or suggestions based upon their own experience. Looking for plugin recommendations.

I have a client who wants users to be able to submit to a simple database. This database only has 6 user fields for each record (name, address, DOB, etc). These 6 fields are details for one record or person. The member can submit as many of these records as possible (which would be as many people they want to submit x 6 fields for each person). Once submitted any other registered user, would be able to login and search ALL submissions to see if there are any matches.

I assume I need a database plugin and a membership plugin. The membership plugin to allow users to register and be able to submit the 6 fields and as many records as they wish. The second plugin to be able to set up a simple database where the user can submit these 6 fields I set up (name, DOB, address, etc). So when ANY registered and logged in user does a search, it pulls up ALL records submitted by other users that match.

Any suggestions for the plugin/s to get this done. I assume the simple database plugin is going to be the most difficult. To set up a database, search fields and enter 6 fields per user, and as many of these as each user wants to enter. Based upon their ability to login first and then submit the data.

Suggestions? Thank you.