your domain is not black listed.. It is not white listed!
If you register a new domain today it will still not work as it's not on the 'white list'!
If your SPF record is correct, the email should still showup in the 'Bulk' mail.
Are you sure your SPF record is okay?
A way of seeing this is by looking at the headers of a Gmail account!
It should say something like this:
Received-SPF: pass (gmail.com: domain of firstname.lastname@example.org designates the_ip_of_server as permitted sender)
is the email address of the sender and the_ip_of_server
the IP of the server running the mailserver.
If the SPF record is wrong the message is like this:
Received-SPF: neutral (gmail.com: the_ip_of_server is neither permitted nor denied by best guess record for domain of email@example.com )
note the neither permitted nor denied
When it's like this I also can not send to Hotmail!