goodroi - 12:14 pm on Nov 22, 2011 (gmt 0)
Google wants to know that if they allow you back in there will no future trouble. Make sure to convey the internal steps you are taking to avoid this.
If the paid links are pointing to internal pages (and you have no control over the links) consider changing the urls and making the links go to a 410. Its one way to show you really don't want these links but it might not be the best way for your site.
Telling Google it was external sabotage (even if it is the truth) might not make Google feel comfortable enough to let you back in since spammers would lie and say the same thing.