The most important factor here is the notion that you can go to one source for a high volume of links where the cost per link is next to nothing. We can argue about what "next to nothing" means, however essentially if any link is not placed on a site or directory where the quality, uniqueness, authority, relevance or trust of that site / directory are strong, that individual link is suspect.
While it can be argued that a new site / directory doesn't yet have authority and thus such a site /directory can still be okay to get a link from, it means the other four signals need to be that much stronger to compensate for that lack of authority.
If the company claiming to offer these services is willing to provide you a spreadsheet listing all the directories they intend to get links for you, go ahead and look at some of those and judge for yourself.
Directories are held to an even higher standard in regard to relevance and trust because the overwhelming majority of "directories" out there are craptastic bogus scams created purely for SEO.
Of the hundreds of thousands of links I have reviewed during client audits this year, I can assure you only a small fraction of links from directories were real, and even a smaller fraction of those provided any value.
Do not get caught up in marketing nonsense. Everything you listed in their claims about why you should trust them is a massive red flag to me that you'll get ripped off.
On a final note, while I am delighted that the previous answers here paved the warning way before I joined this discussion, I need to speak up about the potential for harm. The potential for a penalty here is ALARMINGLY HIGH.
Relying on directory links from a company like the one that pitched you is EXTREMELY DANGEROUS in 2013. Most of the site owners who hire me to do a forensic audit have been penalized manually or algorithmically and most of those have had ugly directory link based inbound link profile madness.