Problème d'envoi sous Outlook 2003 (et autres versions)

Lorsque j'utilise ma messagerie depuis mon ordi à la maison (connecté avec une Livebox de chez Orange) pas de problème, ça baigne.
Etant un gand itinérant, je me connecte sur d'autres réseaux (réseaux d'hôtel, réseau 3G, réseaux d'aéroport) et là, problème: je peux télécharger mes messages sous outlook (2003 ou 2007, c'est pareil) ... mais dès que je veux répondre ou écrire à quelqu'un, j'ai un message d'erreur du genre:
"Certains des destinataires ou tous les destinataires n'ont pas reçu votre message.

Objet : RE: projet d'édito
Date : 17/03/2009 13:26

Impossible de contacter le(s) destinataire(s) suivant(s) :

'UNTEL' le 17/03/2009 13:26
554 5.7.1 <untel@domaine.fr>: Relay access denied"
J'ai bien la solution c'est d'envoyer le message depuis le webmail d'orange, mais c'est bien lourd... est-ce que je loupe pas réglage par hasard.
Merci à ceux qui m'aideront.
Et ALLEZ DAX puisque je suis un supporter des "culs rouges"