La mejor forma es usar un servicio SMTP externo al de tu hosting, yo prefiero el de
www.gmail.com.
en PHP puedes usar la clase PHPMailer que funciona en la mayoria de los hostings gratuitos, en el que he probado es en
www.awardspace.com y en
www.byethost.com
si googleas un rato encontrarás más info sobre la clase PHPmailer.
En cambio, si usas ASP, yo te ayudo a hacerlo usando CDOSYS.