Tickets 8930, 8931, and 8935 have solved most of the problems mentioned here. (8931 actually solves the wrinkle that I previously said could not be ironed out; Isaac had the clever idea of checking the cache by second ticket rather than client name.)
It remains to be determined whether qualify_shortname should default to the primary DNS search domain or "". Either setting should work much better with these changes.