IF your IP was blacklisted, changing the SMTP server won't save you. I suggested trying a different SMTP server because you said only hotmail was blocked.
My blacklist experience is that it starts as one or two domains being blocked, and gets worse until the problem is fixed, and then takes up to a week as the blocked domains gradually begin to accept your mail.
Single blocked domains are mostly related to a DNS server somewhere not handling your mail, thus the attempt to redirect via different servers.
Did you resolve the other STMP login issues?
Also, can you connect the SME server somewhere else so it gets a different ip address, or direct connect an XP machine at the current IP and see if it is OK with Hotmail?