maybe give this a go...
Search > All Fields (or retrieve your existing catalog search) > Add > Basic Fields > Email Address > In From Box Type 0* (Zero*) > In To Box Type z* > Add > OK > Apply any other filters etc. (Leave the same if using your catalog search) > OK
... hope this makes sense!
Using the From 0* To z* trick seems to work with most of the text based fields that you can search on for me.
hope this was helpful, would be great if you could let me know how you get on!