Se apri MSN Messenger e vai in: strumenti - opzioni - connessione trovi anche la possibilità di impostare alcuni parametri per l'utilizzo con un server proxy. Hai provato ad impostarli ?