We really need a better & more flexible search.
I would recommend that you store all profile information in the core DNN fields. All default DNN profile fields need to be searchable.
We have just finished a site using the old version & built our own custom search for a client. This searches the DNN core user profile fields fields.
Basic Search: http://www.myerotichobby.com/Providers/ProvidersSearchBasic/tabid/64/Default.aspx
We have a few store procedures that you can use if that helps