Спасибо большое, BSDLamer

да, возможно у меня что-то с DNS и другими записями не правильно настроено.

То есть, я не шлю спам, почти исключил из общения людей с gmail, но в те редкие моменты (раз в день примерно), когда мне надо им что-то послать я делаю обычно даже реплай на их предыдущий емейл и, с большой вероятностью, мой ответ у них маркируется как спам или вообще не доходит.

Что уже обнаружил.

Команда host <мой_статический_IP_адрес> дает очевидно номер contabo сервера, где крутится мой VPS, но не домейн с е-мейла. Скажите, пожалуйста, а это критично, чтобы домейн, с которого я слал бы почту совпадал бы с DNS - просто каждый IP денег стоит и не сильно хотелось бы платить за 11 статических IP адресов.

Как оказалось SPF, DKIM, DMARC все в красной зоне - я про них не знал, спасибо огромное, что сказали правильные ключевые слова! Скажите, пожалуйста, есть ли какие-то разумно описанные ресурсы, где написано как это самому исправлять не прибегая к оплате специалистов, хочу сам разобраться и попытаться все сам настроить.