Phil,
1) можете попробовать узнать заранее, какой адрес вам смогут предоставить и пробить его по базам;
2) думаю, одного smtp-сервера недостаточно, почтовый сервер реципиента принимает решение о том, считать спамом письмо или нет, основываясь на многих критериях, корректность smtp-сервера отправителя - только один из них.
Phil, с динамическим айпи, как уже заметили выше, беда - для него не удастся корректно прописать PTR/SPF, поэтому если корректная доставка писем не в спам для вас критична - ищите возможность пользоваться для этого именно статическим адресом. Удаление из блэклистов в вашем случае - вопрос вторичный.
Очень даже влияют черные списки, у того же постфикса по умолчанию в конфиге стоят правила блокировать всех тех, кто в этих списках. Надо устранять причины появления своего адреса в них и удалять свой адрес из списков, обычно это просто и бесплатно.