I help moderate a relatively busy forum, sever hundred thousand active users, let me share some of our insights.
It sounds like you have links in posts being followed, no follow all links in posts no matter who posts them. For footer signatures, make a threshold, say 25 posts before the user can have a footer signature. If you want to give people more incentive to post, have a do follow link in their profile after a certain threshold has been passed, like Moz does.
Fighting forum spam is a full time job almost, but it is easier to beat it in the beginning than just handle it as it comes in. Create a honey pot on your registration form and change it out weekly. Something like this could work, http://solutionfactor.net/blog/2014/02/01/honeypot-technique-fast-easy-spam-prevention/
As for the links on the other sites I would disavow them, but once you stop the spam, they should stop. What they are doing is called link laundering. They are placing a link in your forum, then they are using a service like fiverr or similar to build backlinks to the forum link. They do this in hopes to raise the authority of the forum post and in turn raise the authority of links pointing to their site. They are pretty insulated from penalties by doing this, but they risk you getting a penalty.