Для любого, кто придет к этому в будущем для более новой версии Ubuntu, ответ NikTh работает, но вы хотите искать коммерческие, а не независимые.
Это исправило проблему для меня.
Вы проверили количество успешных поставок получателю из вашего постфикса?
Возможно, что получатель в gmail получил слишком много сообщений из других источников.