Benutzt du eine gültige Absenderadresse bei deinen Mails? (Stichwort SPAM-Filter)
Wenn die Absenderadresse gültig ist: Ist der Rechner berechtigt, Mails für die benutzte Absenderadresse zu verschicken? (Stichwort SPF)

Wenn ich die Log-Meldungen oben richtig interpretiere, ist qmail auch irritiert, weil es zwar für den Host 1234567.meinserver.net zuständig ist, diese aber wohl nicht in qmail konfiguriert wurde. (Wenn ich allerdings nachschaue, gibt es zwar einen MXer für meinserver.net, aber keinen für 1234567.meinserver.net.)