If you are using the hyphenation plugin, that corresponds to what I would have guessed the problem is... you are searching for
where the actual text is (unicode hyphens depicted as asterisks)
Code:
foo*bar*with*randomly*interspersed*hyphens
And you need to actually match the hyphens as well.
IIRC, calibre's Edit Book should show invisible characters as yellow spaces.