How do I build a JSON object to send to an AJAX WebService?

The answer is very easy and based on my previous posts Can I return JSON from an .asmx Web Service if the ContentType is not JSON? and JQuery ajax call to httpget webmethod (c#) not working.

The data should be JSON-encoded. You should separate encode every input parameter. Because you have only one parameter you should do like following:

first construct you data as native JavaScript data like:

var myData = {Address: {Address1:"address data 1",
                        Address2:"address data 2",
                        City: "Bonn",
                        State: "NRW",
                        Zip: "53353",
                        {Code: 123,
                         Description: "bla bla"}}};

then give as a parameter of ajax request {request:$.toJSON(myData)}

$.ajax({
    type: "POST",
    contentType: "application/json; charset=utf-8",
    url: "http://bmccorm-xp/HBUpsAddressValidation/AddressValidation.asmx/ValidateAddress",
    data: {request:$.toJSON(myData)},
    dataType: "json",
    success: function(response){
        alert(response);
    }
})

instead of $.toJSON which come from the JSON plugin you can use another version (JSON.stringify) from http://www.json.org/

If your WebMethod had parameters like

public Response ValidateAddress(Request request1, Request myRequest2)

the value of data parameter of the ajax call should be like

data: {request1:$.toJSON(myData1), myRequest2:$.toJSON(myData2)}

or

data: {request1:JSON.stringify(myData1), myRequest2:JSON.stringify(myData2)}

if you prefer another version of JSON encoder.