Yes we had a customer on 139.81.142.31 who signed up for our services just to send spam. We have cought him despite all his tricks the same day we got first complaints. it was on 23 February. We had to be delisted from spamcop blacklist in 48 hours and spamcop's site shows that we are not balcklisted.
http://www.spamcop.net/w3m?action=checkblo...p=139.81.142.31
But there are some providers (we aware only about 2 and already emailed them) who did not update their blacklists and still block mail from this ip. The simplest solution is to wait untill they will be so kind to update their blacklists. I guess they should to do it soon.
Or if you cannot wait we can move your account to other server. There should not be any downtime during account move cpanel can automatically copy files to other server and we'll just change ip in nameservers to point to other server.
The bad thing about spammers that it is hardly possible prevent spam without creating problems for valid users and we just can react to the abuse reports about spammers.