We are having some weird "Undelivered Mail Returned to Sender" errors.
Weird because it only kicks in when mails are targeted at some given domains (gmail.com is one).
Weird because there is no error specified in the non delivery notification.

Example :

Code:
This is the mail system at host ztmk.getalinks.fr.

I'm sorry to have to inform you that your message could not
be delivered to one or more recipients. It's attached below.

For further assistance, please send mail to postmaster.

If you do so, please include this problem report. You can
delete your own text from the attached returned message.

                   The mail system

<example@gmail.com>: gmail.com
All I see in logs is that it gets bounced, but not quite sure from where / what service.
From the various tests I've been through, I'm pretty sure the Zimbra install doesn't even try to reach the target smtp server before the error shows up.

Here are the logs from a failed attempt :

Code:
Oct 17 09:16:13 ztmk postfix/smtpd[4882]: connect from ztmk.getalinks.fr[192.168.101.23]
Oct 17 09:16:13 ztmk postfix/smtpd[4882]: EF87CA5BBB: client=ztmk.getalinks.fr[192.168.101.23]
Oct 17 09:16:13 ztmk postfix/cleanup[4885]: EF87CA5BBB: message-id=<0153b3e1-8d15-479f-a06c-d022e526a6af@ztmk>
Oct 17 09:16:13 ztmk postfix/qmgr[26619]: EF87CA5BBB: from=<admin@ztmk.getalinks.fr>, size=575, nrcpt=1 (queue active)
Oct 17 09:16:13 ztmk postfix/smtpd[4882]: disconnect from ztmk.getalinks.fr[192.168.101.23]
Oct 17 09:16:14 ztmk amavis[26369]: (26369-03) ESMTP::10024 /opt/zimbra/data/amavisd/tmp/amavis-20121016T233006-26369: <admin@ztmk.getalinks.fr> -> <example@gmail.com> SIZE=575 Received: from ztmk.getalinks.fr ([127.0.0.1]) by localhost (ztmk.getalinks.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP for <example@gmail.com>; Wed, 17 Oct 2012 09:16:13 +0200 (CEST)
Oct 17 09:16:14 ztmk amavis[26369]: (26369-03) Checking: km+epEeT4CD4 MYNETS [192.168.101.23] <admin@ztmk.getalinks.fr> -> <example@gmail.com>
Oct 17 09:16:14 ztmk postfix/smtpd[4887]: connect from localhost.localdomain[127.0.0.1]
Oct 17 09:16:14 ztmk postfix/smtpd[4887]: 52755A5C9A: client=localhost.localdomain[127.0.0.1]
Oct 17 09:16:14 ztmk postfix/cleanup[4885]: 52755A5C9A: message-id=<0153b3e1-8d15-479f-a06c-d022e526a6af@ztmk>
Oct 17 09:16:14 ztmk postfix/qmgr[26619]: 52755A5C9A: from=<admin@ztmk.getalinks.fr>, size=1250, nrcpt=1 (queue active)
Oct 17 09:16:14 ztmk amavis[26369]: (26369-03) FWD via SMTP: <admin@ztmk.getalinks.fr> -> <example@gmail.com>,BODY=7BIT 250 2.0.0 from MTA([127.0.0.1]:10025): 250 2.0.0 Ok: queued as 52755A5C9A
Oct 17 09:16:14 ztmk postfix/smtpd[4887]: disconnect from localhost.localdomain[127.0.0.1]
Oct 17 09:16:14 ztmk amavis[26369]: (26369-03) Passed CLEAN, MYNETS LOCAL [192.168.101.23] [192.168.101.23] <admin@ztmk.getalinks.fr> -> <example@gmail.com>, Message-ID: <0153b3e1-8d15-479f-a06c-d022e526a6af@ztmk>, mail_id: km+epEeT4CD4, Hits: -1.105, size: 575, queued_as: 52755A5C9A, 357 ms
Oct 17 09:16:14 ztmk postfix/smtp[4886]: EF87CA5BBB: to=<example@gmail.com>, relay=127.0.0.1[127.0.0.1]:10024, delay=0.38, delays=0.01/0/0/0.36, dsn=2.0.0, status=sent (250 2.0.0 from MTA([127.0.0.1]:10025): 250 2.0.0 Ok: queued as 52755A5C9A)
Oct 17 09:16:14 ztmk postfix/qmgr[26619]: EF87CA5BBB: removed
Oct 17 09:16:14 ztmk postfix/error[4888]: 52755A5C9A: to=<example@gmail.com>, relay=none, delay=0.03, delays=0.01/0.01/0/0.01, dsn=5.0.0, status=bounced (gmail.com)
Oct 17 09:16:14 ztmk postfix/cleanup[4885]: 58D7BA5CBD: message-id=<20121017071614.58D7BA5CBD@ztmk.getalinks.fr>
Oct 17 09:16:14 ztmk postfix/bounce[4889]: 52755A5C9A: sender non-delivery notification: 58D7BA5CBD
Oct 17 09:16:14 ztmk postfix/qmgr[26619]: 58D7BA5CBD: from=<>, size=3081, nrcpt=1 (queue active)
Oct 17 09:16:14 ztmk postfix/qmgr[26619]: 52755A5C9A: removed
Oct 17 09:16:14 ztmk postfix/lmtp[4891]: 58D7BA5CBD: to=<admin@ztmk.getalinks.fr>, relay=ztmk.getalinks.fr[192.168.101.23]:7025, delay=0.07, delays=0.01/0/0/0.06, dsn=2.1.5, status=sent (250 2.1.5 Delivery OK)
Oct 17 09:16:14 ztmk postfix/qmgr[26619]: 58D7BA5CBD: removed
Here are the logs from a successful attempt :

Code:
Oct 17 09:24:02 ztmk postfix/smtpd[7778]: connect from ztmk.getalinks.fr[192.168.101.23]
Oct 17 09:24:02 ztmk postfix/smtpd[7778]: 53629A5BBB: client=ztmk.getalinks.fr[192.168.101.23]
Oct 17 09:24:02 ztmk postfix/cleanup[7795]: 53629A5BBB: message-id=<9e1f6252-3508-4a76-b4f4-5093f0c8744a@ztmk>
Oct 17 09:24:02 ztmk postfix/qmgr[26619]: 53629A5BBB: from=<admin@ztmk.getalinks.fr>, size=573, nrcpt=1 (queue active)
Oct 17 09:24:02 ztmk postfix/smtpd[7778]: disconnect from ztmk.getalinks.fr[192.168.101.23]
Oct 17 09:24:02 ztmk amavis[26375]: (26375-01) ESMTP::10024 /opt/zimbra/data/amavisd/tmp/amavis-20121017T092402-26375: <admin@ztmk.getalinks.fr> -> <example@hotmail.com> SIZE=573 Received: from ztmk.getalinks.fr ([127.0.0.1]) by localhost (ztmk.getalinks.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP for <example@hotmail.com>; Wed, 17 Oct 2012 09:24:02 +0200 (CEST)
Oct 17 09:24:02 ztmk amavis[26375]: (26375-01) Checking: 4ztfFCuVcoCQ MYNETS [192.168.101.23] <admin@ztmk.getalinks.fr> -> <example@hotmail.com>
Oct 17 09:24:02 ztmk postfix/smtpd[7816]: connect from localhost.localdomain[127.0.0.1]
Oct 17 09:24:02 ztmk postfix/smtpd[7816]: 93BF8A5C9A: client=localhost.localdomain[127.0.0.1]
Oct 17 09:24:02 ztmk postfix/cleanup[7795]: 93BF8A5C9A: message-id=<9e1f6252-3508-4a76-b4f4-5093f0c8744a@ztmk>
Oct 17 09:24:02 ztmk postfix/qmgr[26619]: 93BF8A5C9A: from=<admin@ztmk.getalinks.fr>, size=1024, nrcpt=1 (queue active)
Oct 17 09:24:02 ztmk amavis[26375]: (26375-01) FWD via SMTP: <admin@ztmk.getalinks.fr> -> <example@hotmail.com>,BODY=7BIT 250 2.0.0 from MTA([127.0.0.1]:10025): 250 2.0.0 Ok: queued as 93BF8A5C9A
Oct 17 09:24:02 ztmk amavis[26375]: (26375-01) Passed CLEAN, MYNETS LOCAL [192.168.101.23] [192.168.101.23] <admin@ztmk.getalinks.fr> -> <example@hotmail.com>, Message-ID: <9e1f6252-3508-4a76-b4f4-5093f0c8744a@ztmk>, mail_id: 4ztfFCuVcoCQ, Hits: -1.105, size: 573, queued_as: 93BF8A5C9A, 264 ms
Oct 17 09:24:02 ztmk postfix/smtp[7799]: 53629A5BBB: to=<example@hotmail.com>, relay=127.0.0.1[127.0.0.1]:10024, delay=0.29, delays=0.01/0.01/0.01/0.26, dsn=2.0.0, status=sent (250 2.0.0 from MTA([127.0.0.1]:10025): 250 2.0.0 Ok: queued as 93BF8A5C9A)
Oct 17 09:24:02 ztmk postfix/qmgr[26619]: 53629A5BBB: removed
Oct 17 09:24:02 ztmk amavis[26375]: (26375-01) extra modules loaded: /opt/zimbra/zimbramon/lib/x86_64-linux-gnu-thread-multi/auto/Net/SSLeay/autosplit.ix, /opt/zimbra/zimbramon/lib/x86_64-linux-gnu-thread-multi/auto/Net/SSLeay/randomize.al, IO/Socket/SSL.pm, Net/LDAP/Extension.pm, Net/SSLeay.pm
Oct 17 09:24:03 ztmk postfix/smtp[7817]: 93BF8A5C9A: to=<example@hotmail.com>, relay=mx4.hotmail.com[65.55.92.136]:25, delay=1.1, delays=0.01/0.01/0.48/0.65, dsn=2.0.0, status=sent (250  <9e1f6252-3508-4a76-b4f4-5093f0c8744a@ztmk> Queued mail for delivery)
Oct 17 09:24:03 ztmk postfix/qmgr[26619]: 93BF8A5C9A: removed
I went through the zimbra and domain confs all over again but couldn't spot what could possibly cause this issue and being no guru I'm truly stucked now...
Any helping hand would be so much appreciated !

Thanks !