Question is do your customers pay to be listed with you? If so are they using you for the dofollow links? If this is the case then you may lose some of your business by changing it to nofollow.
If they are paying there is also a risk of a Google penalty for paid do follow links.
If you are unable to maintain quality and there is no good reason to have a dofollow, then switch to nofollow.
Are the pages hardcoded? Or is all the data in a database? If it is in a database it would take no time at all to run each domain through a loop and check what response status code you get.http://en.wikipedia.org/wiki/List_of_HTTP_status_codes
This would be a very quick way to find broken links. You may even be able to purchase an api on something like majestic or Moz and run the sites through that as well for a better indication of site quality. If the site has very low DA or Trust Flow, you could also make it nofollow or remove etc...
If it is all hardcoded then that would be very hard work all around.