Aquí tienes videotutoriales que explican como configurar cuentas de correo en los clientes de correo más populares:
http://demodemo.com/tutorials_email.html
Y si estás en un servidor de pago puedes intentar contactar con ellos si sigues teniendo problemas.