Transactional Emails from the server goes directly to Spam folder of users in Yahoo

I am trying to setup our website portal to send registration confirmation emails to customers who sign up (its a simple message containing a link that confirms the email of the user).

Everything is nice and working great, @gmail.com users get the emails okey; however, for @yahoo.com users the email goes directly to Spam folder.

I need to add that I have spend 4 days reading every single forum posting on the subject and have implemented every hint and suggestion possible (note: I am not new to system administration, so I can assure you the time spent was digging rather than learning).

To summarize:

• The sending IP is 64.34.222.102
• There is a proper DNS and rDNS/PTR setup
• The IP is not listed in any of the 100+ black lists I have checked online
• The domain has proper MX entries setup (note: the incoming mail servers run on different IP … can this be a problem? In theory it shouldn't)
• The postmaster and abuse addresses are setup.
• DomainKey is implemented and verified working
• DKIM is implemented and verified working
• SPF is implemented and verified working
• We have signed up for Yahoo and Hotmail Loopback Feed programs
• Here is the site that users Opt-in: www.teltub.com
• I have filled the bulk sender form for Yahoo (it fixed the issue for 3-4 days, but it came back – more on it later)
• Since we are in a test phase, it is extremely unlikely that any of the users actually mark an email as spam (they are mostly friends) and the nature of the emails are not marketing/ads
• Checked SMTP replies from Yahoo, first few days, it included some temporary deferrals but after I filled the forms and signed up with them, it went away.
• Tested a few automatic checkers including allaboutspam.com, all seem good/green: http://www.allaboutspam.com/email-server-test-report/?key=F53F072FADAFE74C8960182016769C56

Three questions I have are:

1. Any idea what am I missing?

2. Someone from Yahoo replied to me that:

   Emails from the mail server(s) you are using have recently become
   de-prioritized due to potential issues with its mailings.

   These de-prioritizations were temporary but may be re-triggered if the
   sending IP profile continues to be poor. Typically, de-prioritizations
   are triggered by bad individual sender or MAIL FROM profiles.

After asking for more details, they said they can not provide any further information!!

3. Yahoo doesn't show the secure key in front of the email … Even if it is assumed spam, shouldn't it display the source authenticity? In another account that a message from this address is marked as "not Spam", it shows the key okey …

Here is the delivery log from postfix:

Oct 18 00:59:25 mgmt postfix/smtp[4321]: 063E0B988A6: to=<for.ehsan@yahoo.com>, relay=b.mx.mail.yahoo.com[74.6.136.65]:25, delay=1.6, delays=0.11/0.01/0.61/0.92, dsn=2.0.0, status=sent (250 ok dirdel)

Here is the message header from Yahoo:

From TELTUB Mon Oct 18 04:59:23 2010
X-Apparently-To: for.ehsan@yahoo.com via 98.136.167.26; Sun, 17 Oct 2010 21:59:25 -0700
Return-Path: <noreply@teltub.com>
X-YahooFilteredBulk: 64.34.222.102
Received-SPF: pass (mta1015.mail.sk1.yahoo.com: domain of noreply@teltub.com designates 64.34.222.102 as permitted sender)
X-YMailISG: HGiMWDwcZAr2nMseAcs8EMjEoTTXRB5jVgymRipvWi77dSrO
 PuvRZPjN1WbGfxHFAyLo99VgChGrTm8Ve_nCA4PLyzhfFKfcsQ8v9FlY3uHJ
 wt3y34DU2ZChx3ud4Scg1ReSSA8b3d3FY5YmWhQDeeckNZUbGYET0MVbjddu
 UX9Z6q3fsIfhsMhedk.6ZT3vsJHs8YiWGcAAiKgipdUnPYhQ36axREymHV8L
 EupzrPp6JE7PM4Ah12Cj8vw8sozDSUiShQM00sD0IC6HUqh4jDRpoISyur.G
 TbHTaa6rZKcNTtaKfE.BRZCJIBQA3oKvFtPt9QZFcDU98adBzlxK8oZxiOuQ
 txWdBWL4zveDo8yqH84sRB2jBLfR8Hig4mZ5bZrUMHnq9P.fNB.6z8XEZoMi
 UBO8eJsYf7Sxug9FtJr9.7.DIRcXshikZker0F0ygc1.ghJwEWLATbGA8UZg
 l2ekjauSWgt1XJQjr9JOpRWwgBTH4N6lXZLE5BQ8q38m6ZspaAZ3glRNSZLU
 YpnRNwRHHy8HLxryXONeR_Q5NcZivZZbof3r2SKvJjZ_DZF9wiuEnlSWng15
 QUd5BAbnA0fSxlaAjS7ayr9HLq0khsSVdlSYeGQpU.3LU6iZt17x3hjZoCXJ
 kB2YBa9ZHH3LkJIezOnNooc9LiYzwnsm1_FaVmvGk1XZzDEsJaadXxtf39o_
 wo2RQVHNaGbt9huEEy4fAiFx6_ZX3pNhepJLnJf2BgNLCi0ix0bw30EPxPPy
 5IaL0vnBeF4S3ReZa2z5cex3apsUULu3vl2zG_HVtsCuvE8-
X-Originating-IP: [64.34.222.102]
Authentication-Results: mta1015.mail.sk1.yahoo.com  from=teltub.com; domainkeys=pass (ok);  from=teltub.com; dkim=pass (ok)
Received: from 127.0.0.1  (HELO mgmt1.prod.teltub.com) (64.34.222.102)
  by mta1015.mail.sk1.yahoo.com with SMTP; Sun, 17 Oct 2010 21:59:25 -0700
Received: from www1.prod.teltub.com (localhost.localdomain [127.0.0.1])
 by www1.prod.teltub.com (Postfix) with ESMTP id DF46118E81BB
 for <for.ehsan@yahoo.com>; Mon, 18 Oct 2010 00:59:23 -0400 (EDT)
X-DomainKeys: Sendmail DomainKeys Filter v1.0.2 mgmt1.prod.teltub.com 063E0B988A6
DomainKey-Signature: a=rsa-sha1; s=teltubdk; d=teltub.com; c=simple; q=dns;
 b=PAHMrH/tt9jRbjOcmeaO6IgbiK+MUfgwP9NZtIMKYNva/ISbDkjUWhHlnbEP1Icji
 axsb+4Q2QrO8zIsT9tWZw==
X-DKIM: Sendmail DKIM Filter v2.8.3 mgmt1.prod.teltub.com 063E0B988A6
DKIM-Signature: v=1; a=rsa-sha1; c=simple/simple; d=teltub.com;
 s=teltubdkim; t=1287377964; bh=xiqqKdrY0J4R8qUgsW9WMXUKnak=;
 h=Content-Type:MIME-Version:Content-Transfer-Encoding:From:To:
  Subject:Message-Id:Date;
 b=q7FEBCnitX/Ohw0RXnjaEZPkXi+hOJHof+hbGarbyC0zWqTpXiknI2bC6k7+QigEH
  ZL4JjzA8WK1MZqSaE6oOjTc3yxy+Dj7niAiB4t5cI8GPvvtegLSO6d2yVTmGa5wDFV
  5f4i5OpHnccPRHkEQ3ShKMzkjKMgVPkdaObAvMFA=
Content-Type: text/html; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
From: "TELTUB" <noreply@teltub.com>
To: for.ehsan@yahoo.com
Subject: This is just a test
Message-Id: <20101018045923.DF46118E81BB@www1.prod.teltub.com>
Date: Mon, 18 Oct 2010 00:59:23 -0400 (EDT)
Content-Length: 111