Аналогично делал отправку почты на сервере Ubuntu (посредством тут же поднятой службы SMTP relay, так как у нас была подсеть из виртуальных машин) и все отлично работало.
Главный вопрос: вы отправляете почту напрямую как и упомянутые почтовые программы (через SMTP) или посредством внешних почтовых программ к которым подключаетесь по COM-соединению? В последнем случае стает очевидной причина, почему на Винде работает, а на Линухе нет :)
Второй вопрос: вы вообще пробовали отлаживать программу и смотреть на текст выдаваемых ошибок? В какой момент происходит ошибка - в момент создания почтового профиля? в момент подключения по этому профилю? в момент формирования почтового сообщения? в момент отправки сообщения по ранее созданному подключению?
Третий вопрос: используете ли вы шифрование SSL? Если да, то с помощью какого сертификата выполняете шифрование - с помощью своего локального или публичного а-ля Mail.RU ?
