Turned out to be a sneaky firewall issue. Thought I'd ruled that out by testing from the command-line, but it turns out there is some kind of hidden proxy that is used by Windows for our interactive logins, but not for the Azure agent. As for why it suddenly stopped working, we think maybe Microsoft changed / added some new ips that weren't covered by our old firewall exception