Mail sendt from my mailserver to Yhaoo.com, Hotmail.com, Gmail.com all end up in spam folder

I have a common problem iguess... when sending mail to Yhaoo.com, Hotmail.com Gmail.com from my mail server(MailEnable 3.10) it all ends up in the spam/junk/bulk folder. Sending mail to rest of the world works fine.

My setup;
I do have a valid PTR record (same as A record)
My IP is not listet in the Spam Database Lookup http://www.dnsstuff.com/tools/ip4r.ch?ip=213.180.86.192
I only allow SMTP relay for authenticated users
I have tested from both my webmail service and from my outlook client, same result...
I have also tested with two different IPs

But still its not working... I'm pretty close to throwing something out the window...

------------- Mail header of mail sent from my troublesome server getting stopped ----------------
From Kim Egenes Fri Feb  8 06:13:44 2008
Return-Path: <kim@webkiosk.no>
Authentication-Results: mta115.mail.re4.yahoo.com  from=webkiosk.no; domainkeys=neutral (no sig)
Received: from 213.180.86.192  (EHLO webkiosk.no) (213.180.86.192)
  by mta115.mail.re4.yahoo.com with SMTP; Fri, 08 Feb 2008 06:13:48 -0800
Received: from ([158.36.103.20]) by webkiosk.no with MailEnable WebMail; Fri, 8 Feb 2008 15:13:44 +0100
To: <kimegenes@yahoo.com>
From: "Kim Egenes" <kim@webkiosk.no>
Subject: Hello there
Date: Fri, 8 Feb 2008 15:13:44 +0100
Message-ID: <5E05244D9EEA4A68A5F901E58BC552F1.MAI@webkiosk.no>
MIME-Version: 1.0
Content-Type: multipart/mixed;
      boundary="--=_Part_6EA993954EBC4E65918CDB4DD8321423"
Content-Length: 257


------------- Mail header of mail sent from my workmail getting through to yahoo.com ----------------
From Egenes Kim Fri Feb  8 06:19:09 2008
Return-Path: <kim.egenes@veths.no>
Authentication-Results: mta515.mail.mud.yahoo.com  from=veths.no; domainkeys=neutral (no sig)
Received: from 158.36.103.101  (EHLO mailscanner2.veths.no) (158.36.103.101)
  by mta515.mail.mud.yahoo.com with SMTP; Fri, 08 Feb 2008 06:19:43 -0800
Received: from nvhmail.veths.no (nvhmail.veths.no [10.77.17.50])
      by mailscanner2.veths.no (Symantec Mail Security) with ESMTP id 878CC2020F
      for <kimegenes@yahoo.com>; Fri,  8 Feb 2008 15:23:16 +0100 (CET)
Content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: multipart/alternative;
      boundary="----_=_NextPart_001_01C86A5D.927E60A9"
Subject: test from work
Date: Fri, 8 Feb 2008 15:19:09 +0100
Message-ID: <F307A63E90E63248B917DF4AF877988D385164@nvhmail.veths.no>
Thread-Topic: test from work
Thread-Index: AchqXZKSe7MqAZ90SySxUDgowarWaQ==
From: "Egenes Kim" <Kim.Egenes@veths.no>
To: <kimegenes@yahoo.com>
Content-Length: 2271

Thanks
Kim