Não uso Locaweb e nunca usei.
Mas eu fico liberando IP de relays de usuários deles a cada 15 dias porque caíram em listas negras.
Nosso servidor usa o postscreen do postfix, um sistema de reputação à base de um ranking de listas de bloqueio, com apenas 26 listas de bloqueio antispam, e os usuários desse provedor vivem pedindo sempre para desbloquear.
Desde que comprei o server não tenho relatos de blacklist, acho que vc ta usando o servidor relay de maneira errada.
Se não aconteceu com você, vocẽ tem muita sorte.
Basta fazer uma pesquisa "dig" no registro SPF de seu domínio, e vai ver uma infinidade de servidores de relay, que apontam para outros relays, que apontam para outros, etc, até que você desiste de procurar relays.
Mas você nunca vê o relay do seu proprio servidor sozinho.
Aí você cai no relay que eles estabelecem, e você se trona um escudo humano.
Prá você entender o que está acontecendo, pra obter um servidor de spam deles, basta pedir um servidor de "E-mail marketing".
Aí você vai perceber que eles te colocam nos mesmos servidores de relays deles.
Detalhe 1: você paga muito caro por isto! Eles faturam muito com isso!
Detalhe 2: É desmoralizante, mas o STF liberou o spam no Brasil, resultado de pressão gente que fatura muito com spam no Brasil, e os E-mails a partir de agora não podem ser considerados "spam" se contiverem um link para descadastramento. E eles estão aproveitando para faturar desta forma.
Detalhe 3: A Locaweb NASCEU fazendo spam, desde 1998, quando entupia os newsgroups com spam descarado. Eu era administrador de um newsgroup de webmasters, e eu mesmo vivia removendo spam deles.
Detalhe 4: Eles parecem apenas terem prosseguido ininterruptamente com esta prática desde então. E além de faturar alto, usam seus usuários comuns para forçarem os desbloqueios. Isso é o "escudo humano" a que me referi.
Detalhe 5: Porque você não cai em lista de bloqueio antispam, não significa que que os outros não caiam. Essa é apenas a sua parte do mundo que você enxerga, e você não pode generalizar.
Detalhe 6: Se você não é um spammer, tenho certeza de que você não usou *todos* os servidores de relay deles, porque são muitos. Um exagero. E que possibilitam um mascaramento do impacto da situação, para casos como o seu.
Detalhe 7: como se pode perceber, tenho alguma experiência direta, bagagem, e conhecimento de causa para falar a respeito.
Abs,
Netino