Thanks everyone for replying.
I've recently been to a big SEO conference and have some solid information about this field which I will detail here for anyone that is interested.
There are some bad replies to this post with, what I believe to be, incorrect information.
This information is my opinion after learning everything I have.
We have since stopped using the company. As of now, the links still exist.
We have come to the conclusion, that at best, the existing links are doing nothing for us. At worst, they are hurting us a bit, but not to any great extent (otherwise we would've been notified in Google Analytics).
It has been stressed to me over and over again by some high profile experts that link building, as we know it, should not be performed.
Links are important, but they are only important if the links are actually used by real people. We have completely stopped trying to get links from people. We are going to put all our effort and time into building unique, interesting content that people will want to read. Interesting content should generate natural links without any work from us in getting that link. Good content should also generate links and like in social media applications, generating further traffic for us.
No manual link building.
Good quality, unique content.
Links will build themselves.