Good, hard questions here.
My gut instinct is to avoid making category names longer than they need to be, even at the cost of some inconsistency. I'd be inclined not to require a county name unless necessary.
Unless there will be confusion, I'd say use just the city and state, e.g.:
Category:Boston, Suffolk, Massachusetts
Category:Fitchburg, Worcester, Massachusetts
Category:Worcester, Worcester, Massachusetts
Then for counties, use:
Category:Suffolk County, Massachusetts
Category:Worcester County, Massachusetts
The hard case you bring up, where there are two towns with the same name in the same state, should be unusual. To avoid confusion I think they'd already be using something, e.g. calling one "Lincoln" and one "Lincoln Township" or one "Croton Falls" and one "Croton on Hudson". And if not, then use the county.
I think only using counties when necessary would save a lot of keystrokes and be easier for people to do. But maybe I'm wrong.