The state drop down can be a hard to cleanup because like you mention their are multiple entry points for that.  The easiest way I do these type of cleanups is use the List screen and add that column and then filter by the ones you want to cleanup.  Once you clear it off all records it will disappear from the drop downs.  

Thanks. Bu this will mean manually adapting  through thousands of records because this is shared by customer, vendor, jobs, contacts (even including inactive ones). It is nçot onl the State field but also country and city with erros piled up over years... All of this is also captured in the address.dat file so I am still hoping there is an easy way to clean that file in one go.

There is actually a 3rd party utility that would streamline this cleanup, you can reach out to me directly and I can send you a link to it.