So I connected to the server via VNC or Remote Desktop and after hours spent without a clue, I tried a "netstat -n" command from DOS prompt and I got an infinite list of TCP/IP ports are in a TIME_WAIT status...
So, what is happening? It seems that there is a strange bug that sometimes Windows does not reuse socket ports in TIME_WAIT status, so when it reaches the maximum port number (65000 or so), the server cannot anymore create new sockets (beware that listening sockets are Ok, so You can connect to the server and all inbound connections actually work, only outbound are rejected).
At this point the only solution is the reboot of the server.
Microsoft has a bug fix but it needs reboot as well:
http://support.microsoft.com/kb/2553549/en-us