Проблема была со способом, которым MSE работает с прокси. К моему удивлению это не делает просто берет настройки прокси от IE, но требует волшебной команды (для Windows 7):
netsh winhttp import proxy ie
Детали здесь.
Даже при том, что мой прокси был установлен в прозрачном режиме, и выше команды сообщает, что прямое подключение используется.