I have researched the plugins that allow the searching for members and I found that this plugin is great but unfortunately the requirements of my client need a lot more customization and I find the documentation of buddypress much more helpful.
About the: xprofile_get_field_data( $field, $user_id = 0, $multi_format = 'array' )
I think using that in a Query would be very expensive as it would require doing more database transaction over the search transaction. Am I right?
The wild card seems like a decent way to go with it, I think I will try that 🙂