Frontend profile search problems
I just successfully replicated this as well.  You've found a bug!

You can report this at http://issues.civicrm.org.  See the page "Reporting a bug", starting with step 7.

That said - "CiviCRM is free to use, but not free to write."  Given the limited resources of the core team, they're very unlikely to fix this without someone stepping up to help with either money or a fix.  That's the economics of free software!  So your choice from here is to:


Submit this to the paid issue queue.
Fix the bug yourself, or, assuming you're not a programmer, find someone to fix this bug for you.  Submit the fix to the core team via Github.
Work around the bug.  Maybe you can restructure your data.  If you were using Drupal, I'd recommend using Drupal Views integration, but unfortunately there's no real equivalent to Views for Wordpress.