Why are my emails being treated as spam by hotmail?

[YellowStarS2k]

I was soon to go live, so I made one live transaction with a real customer.
Everything went smoothly, until my emails were returned to sender.

The emails used to be sent via PHP, but now are being sent through smtpauth. My email was still rejected by hotmail even though it was changed to smtpauth.
Also, the "Emails must send from known domain?" is set to true and MIME HTML is set to false.

My next step will be to make that petition to postmaster.live.com, but who knows how long that will take...

Any suggestions to have my emails not be rejected by hotmail?
Thanks,
Joey

This message was created automatically by mail delivery software.

A message that you sent could not be delivered to one or more of its
recipients. This is a permanent error. The following address(es) failed:

XXXXX##########################
SMTP error from remote mail server after MAIL FROM:<[email protected]> SIZE=2392:
host mx2.hotmail.com [65.55.92.136]: 550 OU-001 Mail rejected by Windows Live Hotmail for policy reasons. Reasons for rejection may be related to content with spam-like characteristics or IP/domain reputation problems. If you are not an email/network admin please contact your E-mail/Internet Service Provider for help. Email/network admins, please visit http://postmaster.live.com for email delivery information and support

------ This is a copy of the message, including all the headers. ------

Return-path: <[email protected]>
Received: from nobody by milky.cirtexhosting.com with local (Exim 4.69)
(envelope-from <[email protected]>)
id 1MC2m9-0006EX-Py
for XXXXX##########################; Wed, 03 Jun 2009 22:33:53 -0400
To: XXXX##########################
Subject: Order Update #5
X-PHP-Script: www.js2k.com/admin/orders.php for 72.181.185.191
Date: Wed, 3 Jun 2009 22:33:53 -0400
From: Joey's S2000 Accessories <[email protected]>
Reply-to: Joey's S2000 Accessories <[email protected]>
Message-ID: <[email protected]>
X-Priority: 3
X-Mailer: PHPMailer [version 1.73] via Zen Cart
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Content-Type: text/plain; charset="iso-8859-1"

Joey's S2000 Accessories
------------------------------------------------------
Order Number: 5

Detailed Invoice:
https://www.js2k.com/index.php?main_...nfo&order_id=5

Date Ordered: Wednesday 03 June, 2009

Your order has been updated to the following status:
New status: Update

Please reply to this email if you have any questions.

This email address was given to us by you or by one of our customers. If you
feel that you have received this email in error, please send an email to
[email protected]
This e-mail is sent in accordance with the US CAN-SPAM Law in effect
01/01/2004. Removal requests can be sent to this address and will be honored
and respected.

[YellowStarS2k]

Also blocked by Yahoo mail...
Yahoo says to refer to Spamhaus SPL to see if my mail server is listed as a spam originator, and sure enough it is.
http://cbl.abuseat.org/lookup.cgi?ip=208.53.168.58

I guess it's up to my webhost to deal with the issue?

ARGH this is a PITA.

[YellowStarS2k]

Order confirmation emails are also treated as spam

This message was created automatically by mail delivery software.

A message that you sent could not be delivered to one or more of its
recipients. This is a permanent error. The following address(es) failed:

xx
SMTP error from remote mail server after MAIL FROM:<[email protected]> SIZE=3224:
host mx4.hotmail.com [65.55.92.168]: 550 OU-001 Mail rejected by Windows Live Hotmail for policy reasons. Reasons for rejection may be related to content with spam-like characteristics or IP/domain reputation problems. If you are not an email/network admin please contact your E-mail/Internet Service Provider for help. Email/network admins, please visit http://postmaster.live.com for email delivery information and support

------ This is a copy of the message, including all the headers. ------

Return-path: <[email protected]>
Received: from nobody by milky.cirtexhosting.com with local (Exim 4.69)
(envelope-from <[email protected]>)
id 1MC1lB-0000mm-Lw
for xxxx; Wed, 03 Jun 2009 21:28:49 -0400
To: xxxx
Subject: Order Confirmation No: 5
X-PHP-Script: www.js2k.com/index.php for 64.222.224.36
Date: Wed, 3 Jun 2009 21:28:49 -0400
From: Joey's S2000 Accessories <[email protected]>
Reply-to: Joey's S2000 Accessories <[email protected]>
Message-ID: <[email protected]>
X-Priority: 3
X-Mailer: PHPMailer [version 1.73] via Zen Cart
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Content-Type: text/plain; charset="iso-8859-1"

Order Confirmation from Joey's S2000 Accessories

xxxx

Thanks for shopping with us today!
The following are the details of your order.
------------------------------------------------------
Order Number: 5
Date Ordered: Wednesday 03 June, 2009
Detailed Invoice:
xxxx


Products
------------------------------------------------------
1 x Berlina Black Keyhole Covers = $10.99
------------------------------------------------------
Sub-Total: $10.99
Table Rate (1 x 1.00lbs) (Best Way): $2.50
Discount Coupon: zippy : -$5.50
Total: $7.99

Delivery Address
------------------------------------------------------
xxxx

Billing Address
------------------------------------------------------
xxxx

Payment Method
------------------------------------------------------
PayPal


-----
This email address was given to us by you or by one of our customers. If you
feel that you have received this email in error, please send an email to
[email protected]


-----
Copyright (c) 2009 Joey's S2000 Accessories. Powered by Zen Cart


This email is sent in accordance with the US CAN-SPAM Law in effect
01/01/2004. Removal requests can be sent to this address and will be honored
and respected.

[YellowStarS2k]

Turns out that my host's mail server is blacklisted by multiple blacklists... $(*%&@(#*&$&^%.