Welcome to the hell I've known since March 2012 (and am still there for a couple of sites!). Getting an unnatural links notice doesn't mean your site is going to be deindexed, but your site WILL be penalised for the keywords that Google have collected within those unnatural links it found. It's impossible to say if/when Google will lift the penalty regardless of what you do - I know that's as imprecise an answer as you could get, but that's the nature of the problem - it's down to the discretion of Google. One site of mine had bearly any links pointing to it - I did have control over all those links and removed them all (it was a new site back in March 2012). Several reconsideration requests followed, each and every one of them were replied by Google that unnatural links could still be found. ahrefs, opensiteexplorer disagreed with that assessment - they could find nothing, and I removed all the links I built to the site. Maybe I have some uber-stealthy links pointing to my site undetectable by all but Google?