Personally, I would place a premium on how the wheelbuilder stands behind their wheels. I build wheels myself, and I have a lifetime warranty on all my wheels - meaning I will guarantee anything related to build quality for life (ie truing, replacing broken spokes)(although if the wheel is not local, shipping charges are involved). Wear through a brake track, you are on your own - that is not build related. I would expect the same from any other competent wheelbuilder - that they stand behind their work.
Beyond that, I would ask if they use a tensiometer, and how they balance spoke tension. It is a lot easier to build a true wheel with okay spoke tension than it is to build a true wheel with even spoke tension, that is tensioned to spec. The first wheel would seem great at first, but it would go out of true and/or break spokes more easily. FWIW, the best answer they could give is that they use a tensiometer from a major bicycle components manufacturer, and that they use some variant of the Park TCC spreadsheet (for more info on this: )
http://www.parktool.com/blog/repair-...lator-for-tm-1).