As Eric Ward says above, no single agency can do it all. Each site needs its own bespoke link building campaign. He is also correct about just how much dross is out there, being sold each and every day, in which 90%+ is absolutely useless.
"If everyone listened more to Eric Ward regards linking, then the web would be a better place." (Yes, you can quote me, Eric!)
Most of the ones that do listen try and forget what he says, because he tells them what they need to know, but this means hard work. So, they end up using other schemes. For the ones that listen AND action, well, lets just say that they are the people that are happy on the web.
Anyway, enough of making Eric feel good... :-)
If you want a company that uses legitimate techniques, the very first one that they should offer is to ask you just why you think you should be linked to. What content do you have that is so good that other websites should want to list it on their own site? If they ask you this, and you can answer honestly, either positively, or negatively, then you are on the right track.
If you do not have this content (a great blog, a directory of related services to your industry, the best glossary in your industry, some great tools etc), then you had better get some, otherwise the $$$$ you spend on linking could become one of the worst decisions you ever made.
There are so many things to explain, but this should be enough to get you started.
James