Never mind, I figured it out:
My developer machine has MSXML 4 installed so I was using
Server.CreateObject("Msxml2.ServerXMLHTTP.4.0")
Apparently, server has an older version of MSXML (3?). Once I got rid of "4.0" everything started to work:
Server.CreateObject("Msxml2.ServerXMLHTTP")