Your first code block is correct.
Set webreq = Server.CreateObject("MSXML2.ServerXMLHTTP.4.0")
webreq.open "GET", searchURL, false
webreq.setRequestHeader "Authorization" ,"Basic " & base64Encode(":" & MyNewKey)
webreq.send
The response is: 400: The provided format is not supported.
400 means the query you are using is invalid. "The provided format is not supported." means the value you provider after $format is invalid.
Can you share the query you were trying to make?