Зная многих знакомых и как блочат сервера по первой жалобе не разобравшись
Если ваши знакомые не смогли найти источник - это не значит, что его нет.
1)для этого необходим установлен и настроенный почтовик?
Нет. Вам вполне могли закинуть скриптец, который умеет отправлять письма без MTA.
2) Как правильно им ответить, чтобы они не заблокировали сервер, на котором админ не прикасался к почтовику.
Тут главное не отмалчиваться, а выйти на контакт с поддержкой. Им блокировать всех клиентов подряд тоже нифига не выгодно.
Если почта вам не нужна, то можете заблокировать исходящие соединения по 25 (можно и 465 до кучи) порту в фаерволе и об этом и написать. Но лучше поискать откуда могла происходить рассылка и устранить причину. Жалобы совсем без причины если и бывают, то очень редко.