If I search for a contact's email from the web interface I find the matching contact.. However, if I search from the REST interface using POSTMAN or CURL I get zero results. The query works, just doesn't return any records.
According to the help this should work:
Specifically, what I get back is this: