Была похожая ситуация.
Решал ее так:
1. Узнал от какой службы приходят письма(из заголовков письма) — например
Received: from user37 by exampleservice.com with local (Exim 4.74)
(envelope-from <somebody@spamfromthis.email>)
id 1Rgskc-0008Hw-GD
for me@myemail.com; Sat, 31 Dec 2011 08:49:06 +0200
2. Писал письмо-жалобу на пользователя за СПАМ(адрес брал с сайта службы). Если надо отправлял заголовки писем для доказательства существование писем
3. Если никто ничего не предпринимал насчет пользователя то с помощью 2ip.ru узнавал у кого стоят сервера компании и писал хостеру.
В моем случае сайт-владелец почтовой службы никак не отреагировал(так как был служебным одной фирмы) зато хостер(в моем случае ДЦ Воля) отключил сервера, так как я был не один кому приходил СПАМ
