I've used some of the domain negotiating services, though only for private domains. You can always make a direct offer to the private registration companies, if you don't want to go the negotiator route.
In my experience, you just have to start the process w/ a serious offer. You have a pretty good starting point w/ Brad Feld's blog, so a 1-2k offer is as good a place as any to start.
On the flip side, start with the highest number that if someone offered to sell you the domain at that price, you'd buy it as a no brainer. Best of luck.