>Вот мой вопрос в том и состоит: почему другие SMTP-серверы (не имеющие к ukr.net никакого отношения), успешно шлют на него письма, а у меня не получается?

1. А может все-таки где-то в командах HELO или EHLO/MAIL FROM/RCPT TO апшипочка???
2. А к этим серверам ты не через прокси ли какой-нибудь выходишь? Как тебя снаружи видно? Под тем ли IPшником?
3. А что ты ставишь в MAIL FROM ? IPшник или имя хоста?