I have had problems sending e-mails from my e-mail client (Windows Live Mail) and must admit that firstly I suspected the Microsoft product as the problem. Well that fact that Microsoft often is blamed for things which actually not is their fault is another story!
I asked the support from gullestrup.net and they suggested that it was my internet service provider (Danish company TDC). Sometimes they block traffic on the default port 25 (used for outgoing traffic), so I simply should change port for outgoing traffic to 26.
So today I changed changing it under the Account advanced settings in Windows Live Mail, and voila! I can send e-mails again!