One would think that calling CContact.NewAddress("somePurpose") would give you a CAddress with the purpose you specified.  However, that is not the case.  The following NUnit demo passes:

[Test, Explicit("Just a demonstration of weird iMIS behavior.")]
public void Demo_NewAddressDoesNotSetPurpose()
{
    var imisContact = new CContact(user)
    {
        Prefix = Prefix,
        FirstName = FirstName,
        MiddleName = MiddleName,
        LastName = LastName,
        Suffix = Suffix
    };

    var address = imisContact.NewAddress(TestAddressPurpose);
    var actualPurpose = address.AddressPurpose;
    Assert.IsEmpty(actualPurpose);
}

Look at the method in Reflector; unless the Purpose is a special value (one of the 3 special "default" address purposes, I'm assuming), the purpose you specify is basically ignored.  You have to set the AddressPurpose property separately:

var newAddress = CContact.NewAddress(purpose);
newAddress.AddressPurpose = purpose;