I can probably help you with this solution.... I run my own server, hosting around 50 websites (99% uptime over the last 3 years+) . I have an open source content management system (CMS) that I use called Joomla! which has a component available for it called Community Builder (CB). Suffice it to say, it gives you a website that people can log into, with just using the CMS, but with the CB system, it gives you the profiles you want to be able to search.

Joomla! can be demo'd at their site: http://joomla.org
Community Builder's site: http://www.joomlapolis.com

They are both free to use, you would just have to learn how to set them up and configure them both. It's tricky at first - I still install all the sample data as it's even harder if you do not (I just adjust it accordingly).

I have no experience using a thrid-party webhost for the install, as I said above I own my own commercial server, but can't imagine it would take that much to get it installed (there are support forums to help decide on a host). You just need FTP access to install, or server admin access.

One site I manage is for MemoryMan.com. He is so far the only one who needed Member access. You can see how it appears at http://memshop.memoryman.com. The menus appear on the left, once logged in as a member, there is a Member's Only area.

I have not yet used CB myself (I am in the process of setting a site up for a client now), but their website seems to describe exactly what you need.