Как часто банят спамщиков?

Надеетесь, что тут сидят спамеры?) )
Это скорее в категорию "Программирование".
"Устанавливать" прокси бесполезно. Куда? На свой компьютер? И как он тогда адрес скрывать будет?
"Соединяются с прокси-сервером" имелось в виду, наверное?
Да без разницы - с платным, или бесплатным. Лишь бы протокол поддерживал (POP3/SMTP - для рассылки почтового спама по этим протоколам) и был анонимным. Как вариант - ремейлеры (анонимные сервисы отправки почты) .
Для всяческого спама через веб-интерфейс (спам по блогам, форумам и т. п. ) используются HTTP-прокси.
Но по IP банят без разбора только самые дикие почтовые сервисы типа Mail ru
Ситуация такая - на одном IP-адресе висят десятки сайтов (на "обычном" виртуальном хостинге) . С одного из них рассылаются спамерские сообщения (взлом, дырявый скрипт, или хозяин-бяка) . Банится IP-адрес сервера на почтовом сервисе - и на этот сервис никому не придет больше почта ни с одного из сайтов на этом сервере.
Не раз уже попадали в такую ситуацию с mail ru. Поэтому клиентам крайне не рекомендуем держать основную почту тут.
Если речь про обычные рассылки с компьютера, то большинство адресов выделяются из блока провайдера динамически. Спамер сидел на одном IP, переподключился к сети, или перезагрузился - адрес уже другой. А старый достался какому-то неудачнику...) )
Банить по IP в этом случае бесполезно, а поймать - можно.
В вопросе лучше было бы уточнить - про какой спам идет речь.
Мне по барабану спамеры - фильтры +Gmail и если одно из 20 писем пролезет, то уже чудо. Но я ж его даже не открою...

через операторов мобильной связи или же зомби сети