Sua pergunta é um pouco incerta: você diz que "eles têm algum tipo de mala direta em massa que é spam". Eu suponho que você quer dizer que não é intencional. Todos os e-mails são enviados pelo servidor (verifique as filas e isso é um servidor do Exchange 2003)? Também não está claro se esses 6 computadores clientes estão enviando spam pelo Exchange Server ou se estão enviando diretamente para a porta 25.
Eu vi o Exchange 2003, totalmente corrigido, configurado tecnicamente corretamente, ainda ter furos que permitiram relés. Os patches posteriores os corrigem, mas não conte com isso agora. Eu definitivamente estaria planejando mudar para o SBS 2011, mesmo que você não o faça imediatamente.
Eu estou com os outros caras: Eu tenho uma regra de firewall que SÓ deixa a saída do servidor de e-mail 25 de saída e uma regra de negação explícita para todos os outros. Assim, mesmo que você receba um vírus de envio de spam em todos os PCs, eles não poderão enviar diretamente, e seu ISP e o mundo não o odeiam. Isso tudo é mais fácil de fazer se você tiver um esquema de IP muito bom, caso contrário, você pode ter que fazer várias regras. Parece que você está infectado de alguma forma, mesmo que você ainda não tenha encontrado.
Para expor o que o gravyface disse, um serviço como o Postini do Google pode substituir seus filtros locais atuais de forma muito barata. Todo o correio entra e sai através deles, e é verificado por SPAM / vírus. Então você pode permitir a porta 25 em APENAS dos servidores do Google no seu firewall, então não há como ser retransmitido, a menos que o Google se estrague de alguma forma. Isso também tem o benefício de que, se você não tiver um registro MX secundário, como algumas empresas de pequeno porte não fazem, todo o email vai para os quatro servidores do Google para os quais você fornece registros MX e, mesmo que o servidor esteja inativo filas até o seu servidor ficar on-line novamente.