Will google impose a penalty due to suspected bad/spammy links and not advise of the automatic and or manual action in webmaster tools?

We have received no formal notification as such but one SEO firm we are looking at hiring has suggested we are being punished for many suspect links. We, like many, have struggled finding a competent and legitimate SEO firm and past exercises may have gotten us to this point but I have no evidence as to whether the statement being made is true or not just the fact that around June of 2012 we started falling way back in a lot of our key phrases. We've made minimal on-page changes since 2011 but we did hire a firm to run with finding and building quality links.

Would love some opinions on the matter and how to really determine what the cause to the effect is so we can move towards remedy. The current firm is also saying that at this point we need to start over with a new URL. We have a 10-year old domain and have moderate to good success over the years. I can't imagine that whether by accident or even maliciously that google's answer to this problem would be ctrl-alt-del.

Thanks in advance,
Seeking Knowledge