[dane-pgp]

Why don't the councils let the people on each half of the street vote for a new name for their half? The two votes could take place years apart, so it doesn't strictly need the councils to be closely cooperating.

I suppose the failure mode would be that one side refuses to propose a new name, and it's unfair to reward that side by letting them keep the existing name. Also, the two sides might both vote for the same new name, but maybe that could be resolved with a coin toss.

Another alternative would be some sort of Dutch auction, where the two sides try to under-bid each other for some cash reward for having their side renamed. Actually running that auction in a democratically legitimate way might be a bit complicated, though, and obviously the money would have to come from somewhere.