As * is a wildcard character that matches any string, it gives me the first row, not the first row containing an asterisks.
Enclosing the asterisk in your search string in square brackets, i.e. "[*]", is in fact the correct answer. This is according to Microsoft documentation. And here's the proof:
Works like a charm! Perhaps what you are missing is the "Any Part of Field" setting?