Email spam problem


I have hosting on hostgator, its great hosting for me, but now i want to enable registrations on site and install xenforo but there is one huge problem for me and that is spam. When someone register or contact me with contact form "wordpress" i get that mail in spam folder, also my users get their activation mail in spam folder. I already contacted hostgator support but i dont know are they lazy or dont know how to help me, anyway their answer is something like "someone from server sended spam and now server is blacklisted" which ofc didnt help me at all. Is there something to bypass this blacklist thing? Thanks-