turbocharged - 12:11 pm on Jul 21, 2013 (gmt 0)
The term you used is appropriate - link directories. I don't know of any link directory that has added links out of their own free will. These types of sites exist from revenue derived from the scarce payment they receive from someone pays to be listed. Normally payment gives better placement too. In other words, if I were a gambling man I would say your client is lying when he said that he did not give permission for the links to be added. He, like many others, probably was using some cheap SEO service that promised quantities of links.
I would advise your client to be very cautious in using threats to remove links. I've heard of a number of cases where those threatened have created thousands of new spam links pointing to the sites wanting their links removed. Use the disavow tool is you must.