One thing I just recalled is that if you maintain a small exceptions lookup table (i.e. the ones that span state boundaries), you can use ZIP Codes as a way to uniquely look up a county name.
I think Zillow does it best. You just type your address in a box and it looks up the normalized full address.
That makes everyone happy.