As an attempt to solve this problem, I've copied the various values in the standard country picklist field to a backup text field so we could go back and clean up later. Now I'm trying to delete all the values in the country/state picklists that don't match the salesforce provided list.
Problem is, I get the same error message about incorrect state/country values when I just try to delete the selection from the country/state picklist field, whether on the edit page or through a data load. This despite the fact that the field is not required on any of my page layouts.
For example, using DemandTools I set the value of the BillingCountry, Billing Country Code, and Billing State/Province and its code, all to constant blank values - but I get the error message saying it doesn't recognize the state/country.
Does anyone know how to wipe out the country values in the standard field in a way that won't give an error message, and act like a newly created record where no value has been entered yet?