В официальной документации говорится о том, что Exim (который по умолчанию установлен в нашем шаблоне debian) - не поддерживается gitlab. А точнее работает, но слегка кривовато (то отправляет, то не отправляет). 
Поэтому было принято решение использовать стандартный SMTP сервер. 
Необходимые действия
Находим блок 
Расскоментируем и исправим всего несколько параметров (для нашего случая)
Используемый сервер SMTP не требует авторизации, внутри нашей сети. 
Строчку 
Необходимо найти выше 
После редактирования конфигурации - необходимо "пересобрать" gitlab:
Теперь уведомления будут корректно приходить. 
