Improving the search is a high priority item for us. We are planning on having more options soon in terms of different fields like dates and locations.
In the meantime, sometimes it's helpful to use the Google search on the search page (at the bottom where it says search for anything). For example, searching for Adams Maine brings up a bunch of people with the last name Adams in Maine. I know it's not as helpful for finding duplicates, but I sometimes find it helpful.