What about something like “expire an entry from the new table if it’s older than a week, and the new table is at greater than 50% capacity” ? Or would that just encourage more address spam and ultimately reach the same state?
We could consider filling the first N slots of a GetAddr response with addresses from Tried.
Perhaps select a random subset (20%?) of the tried table to draw these addresses from, with the subset preserved across restarts?