After lots of Googling, talking on IRC, and futzing with things, I've learned how to get Nominatim to properly link boundaries and place nodes, and thus get addressing to work correctly (at least on the county level). I'm assuming this also works at the city level, though I'm still in the process of fixing Texas counties and haven't tried it with cities yet.
The 'key' is in the names and alt_name, and using the 'label' role on the boundary relation. For example, "Anderson County, Texas" has 'name=Anderson County' and 'alt_name=Anderson', while the county node has 'place=county' and 'name=Anderson". Also, importantly, the county node is a member of the boundary relation, with the role 'label'.
This is how it looks in Nominatim when working right.... the boundary: http://nominatim.openstreetmap.org/details.php?place_id=98191762 the county node: http://nominatim.openstreetmap.org/details.php?place_id=9162125655
This is an example of one I haven't fixed yet, that is still working wrong... the boundary: http://nominatim.openstreetmap.org/details.php?place_id=98029496 the county node: http://nominatim.openstreetmap.org/details.php?place_id=1600889
As you can see, in the one that works right, the county node is listed as a 'linked place' in the boundary relation entry, and all of the places in the county are 'addressed' to the boundary relation instead of split between it and the county node. Also, if you look at the places located in the county, such as http://nominatim.openstreetmap.org/details.php?place_id=2769902 you can see that Nominatim is no longer having to 'guess' at the county addressing, as it's now explicit.
I'm also setting the boundary ways as "boundary=administrative and admin_level=6", but I don't think this is really essential...it's more a backup for if those keys get removed from the relation.
Thanks to the people who've talked this out with me on IRC, and especially lonvia, who gave the final part of getting it to work correctly. Now, we get to fix lots of counties...