trouble sending email to hotmail - receiving a 550 response

One of our clients is having trouble sending email to hotmail addresses.

We are running sbs 2003 and using Exchange 2003 for sending email.

We have occasionally had a few issues with being blacklisted - but at present we are not on any blacklists.

HOWEVER, we are still being blocked by Hotmail - when sending mail to hotmail addresses we get the following error:
550 Requested action not taken: mailbox unavailable

I have tried several hotmail addresses, same problem.

I have also used telnet to communicate with Hotmails Mail servers - it allows the connection, but when trying to enter a recipient address, it produces the same error.

Anyway, I emailed Hotmail, and got a response to confirm that our IP has a poor reputation. They have advised me that we need to join their senderID program, I looked in to this and read up on SPF records - as I understand, these records inform mail servers who has the authority to send mail from our domains.

The problem is, I cannot set up an SPF record as our domains are actually hosted with 1and1 - and they apparently dont allow for this.

My question is, is this imperative in order to send to hotmail addresses, or is there another way to repair our reputation - has anyone else had a similar issue and how did they solve it?

I think my options are either move domain hosting/dns hosting to another provider, or perhaps send mail out through our ISP via smart host - is this a common method? Does it have downfalls? And how exactly is it done?

Thanks!!