jakebohall - 1:36 pm on Aug 21, 2013 (gmt 0)
Would definitely recommend you just adjust your site to no-follow the links, and only link out with the business owners company name, URL, or "company website" style phrase as the anchor text.
It is likely that you are being flagged by SEOs doing link removal because you are using keyword specific anchor text on a followed link, and since you are a directory of sorts, it appears unnatural despite however natural the links may be.
If you have no-followed the link, you have taken care of any issue that could potentially cause an issue for the webmasters writing to you. I don't foresee your mass no-following of these outbound links causing any issue with your own rankings, etc.