¿Por qué no consigo enviar mails cuando utilizo una conexión gratuita de tiscali con outlook?

Hola. Tengo una dirección de una conexión gratuita de Tiscali que quiero usar en el Outlook, actualmente me sirvo de una tarifa plana de Terra; intentando con el saliente de Terra (mailhost) recibo esto:
"ATENCIÓN: Este mensaje no ha sido enviado a su/s destinatario/s porque esta intentando usar el servidor de correo SMTP de Terra, que solo envía mensajes cuyo remitente sea una cuenta de correo Terra. Por favor, cambie la configuración de su programa de correo, de forma que utilice el servidor SMTP asociado a la cuenta de correo con la cual quiere enviar el mensaje"
Y cuando pongo el de Tíscali (smtp) me sale esto:
"El mensaje no se pudo enviar, uno de los destinatarios fue rechazado por el servidor. Su dirección de correo electrónico es "[email protected]". Asunto 'desde tiscali con seu smtp', Cuenta: 'tiscali', Servidor: 'smtp.tiscali.es', Protocolo: SMTP, Respuesta del servidor: '550 RCPT TO:<[email protected]> Relaying not allowed', Puerto: 25, Seguridad (SSL): No, Error de servidor: 550, Número de error: 0x800CCC79"
El caso es que recibo sin problema pero el envío no va. Aunque, u
n día, del modo anterior, envió los mensajes (prometo que no estaba de resaca).
¿Tengo qué dar por imposible el intento? Pienso cambiarme a Ya.com (mejor oferta), ¿tendré el mismo problema?
Gracias por tu tiempo y perdona todo el testamento. Un saludo