Linux - Relay SMTP

Buenas, una consulta, tengo un problema con el envio de correos. Dentro de mi red el envio y recepcion esta ok, pero cuando una persona de fuera de nuestra red quiere conectarse mediante su outlook , puede recibir normal correos, pero no puede enviar, solo envia correos dentro del dominio, pero si quiere enviar a hotmail o yahoo por ejemplo les retorna un mensaje con "relay denied", no se que es lo que me falta configurar en mi correo para que los externos pueden enviar correos tambien. Cualquier ayuda es bienvenida.

¿Qué servidor de SMTP usas?
¿Lo tienes configurado para que permita relay?

Cualquier ayuda es bienvenida.