Può essere che il computer a cui cerchi di inviarlo non abbia il servizio Messenger, ce l'abbia disabilitato oppure protetto da un firewall.
Se ti dice che il messaggio è stato inviato, deve arrivare per forza