Hi Greyhound
I would suggest that you contact their
Web Hosting UK - Free 24x7 Technical Support - Dedicated Server - VPS Hosting Tutorials where you can chat one to one with an advisor
I'm uncertain though that their servers are blacklisted as you suggest, and some domains tend to be over enthusiastic when it comes to how they interpret spam
You mention that you have received lots of spam - have you considered that your domain or email address may have been compromised?