Since the vast majority of domain sales are private (unpublished, unreported) enduser sales there is a HUGE chunk of data missing from the databases of the various automated appraisal services. Lacking that data I believe the automated services will tend to underestimate value in as many cases as they overestimate value. Therefore, while I believe the appraisal services are a good starting point I believe "the human touch" is essential, particularly IF that human has what I'll call market vertical expertise AND has been in the business for about 7-10 years, so he/she has witnessed the ups and downs, the arrival and departure of various valuation "formulas", etc.
So, spend a little but don't except a lot.
In rank of "expertise" I would say:
1. Moniker, IF there is human engagement in addition to any automated system.
2. Sedo, largely automated and the humans can range in quality from very good to staffers that come across as new yet cocky, i.e., more reading about domains than experience in the market.
3. BuyDomains, though no one is impressed with their wholesale purchases. I'm not even sure they offer appraisals but, if they do, that have a lot of data. Their pricing tends towards moving merchandise and they also discount, from time to time, so I would use any estimate as a starting point.
4. GoDaddy? Eh. Since they've been working with Fabulous, selling aftermarket domains, they may have a few more datapoints.
You can also post at various domain forums that allow you to post domain names but the valuations you receive, even amongst experienced domainers, tends to reflect "valuation bias" (those that look to buy in the aftermarket, at wholesale) and - if bias can be put aside - you still see values all over the place.
So, get your appraisal but do your own homework to discern trends (relating to the domain, if generic), etc. A generic domain, for an industry that is "just emerging", is likely worth more than what automated systems will offer as a valuation.