Just to touch base here in this long thread -- I hope these aren't things you've already covered (lots of good feedback is here already). If your site receives a notification of web-spam or manual action in Webmaster Tools, then that will be due to a web-spam review and manual action that has been taken. While manual actions will expire at some point, I would strongly not recommend sweeping them under the carpet and hoping that they go away on their own -- at least if you're interested in having your site be optimally represented in our search results. Even when a manual action expires (which might take quite some time), if the reason for the original manual action is still relevant, it's always possible that the manual action is returned later on. In my opinion, if you're aware of issues that are negatively affecting your site's performance in search, and if its performance there is important to you, then resolving those issues is often a good use of time.
With regards to links, we have to recrawl those linking pages in order to recognize the changes that were made there, but in many cases we're quite fast in crawling and picking up changes. The submit-URL feature is useful for submitting new URLs for crawling and indexing, but won't have a direct effect with regards to how quickly we recognize the links on those URLs (if we've already crawled and indexed them in the past), so it wouldn't help to submit all of those URLs there.