Installing and removing the branding is easy, but you will not be able to change the spam aspect unless you change web hosts.
If you give me the site name, or an IP I might be able to give you more info on this, but it's a really hard problem, it doesn't depend on you (but on third party spam lists). If you're on one of those, is very hard to get delisted and requires your ISP /web host involvement.