Может, вам завести отдельный VPS серверок (любой мощности) только для отправки и переадресации почты на основной сервер. Прописать SPF, что он имеет право отправлять почту.
На основном сервере проверьте по логам, нет ли странных авторизаций, отправок писем. Лог максимально подробно настройте. На вирусню проверьте сервер почтовый. Чудес не бывает. У вас Windows, вирусню подхватить легче, особенно если Windows лицом в мир стоит.
Вкратце, у вас должна присутсстовать SPF-запись в DNS, корректная запись в обратной зоне DNS (у провайдера). Приветствуется наличие DMARC и DKIM - будет плюсом при проверке писем на спам.
Это всё так, но не факт, что, к примеру, ваш IP (или подсеть) не были скомпрометированы предыдущими пользователями. А, главное, не надо рассылать спам :-)