There are a number of solutions proposed, but it seems like there might be a simpler solution to make the selection of peers more random.
As I understand it, the attack relies on an attacker being able to connect to a specific target node.
Wouldn't either of the following two solutions work?
Differentiate between input and output peers. Allow anyone to connect to you to receive information from you but only take information from peers that you connect to. This would make it very difficult for an attacker to have a large number of connections to a specific node because the node is randomly choosing which nodes to receive data from.
Continuously change connected nodes. i.e. every minute or so, disconnect from one connected node and find a new one to connect to. This would create a constant rotation of nodes that would make it much harder for an attacker to keep his/her connections to your node.
Solution number 1 would mitigate this problem, but the attacker could try creating enough nodes to flood the network anyway (see cancer nodes). It would not be likely that the attack would be performed, but it would still be possible.
Solution number 2 would help with this problem, although it would cause a lot more problems with everything else. Imagine the excess traffic caused by tens of thousands of Bitcoin clients dropping all of their connections each minute and reestablishing them with new peers. You would need to exchange a lot of information this way you wouldn't normally have to (version, verack and inv messages during each such reconnection at the very least). As the attack does not appear a likely threat for the Bitcoin network, such overhead would be unjustifiable.