So here is something very strange. All of a sudden, Msg Plus Live can contact my mail server, and nothing has changed. I had verified that my mailserver was up at the time, by going into my mailbox and our public mail folders (We use Exchange 2003 here).
I don't know what happened, but oh well, at least it works now.
/ 
