spam problem == bad management
Is this the same company as Carphone Warehouse Broadband Services? I had to block SMTP contact from their network, 126.96.36.199/11. Tons of bot spam coming in from there, and their IETF RFC 2142 abuse address ignored complaints or didn't work. None of my users has ever complained about this block.
In general, I have found spam response to be a pretty good indicator of management quality. Well run companies do not have an outbound spam problem. Companies who refuse to control their outbound spam tend to have ethical and competence issues company-wide.