Eu finalmente descobri a resposta certa para essa.
Resposta curta: Conflito de endereço MAC.
Resposta longa: Para cada máquina virtual, o qemu cria uma placa de rede virtual. Ele atribui um endereço MAC a essa NIC virtual. Por padrão, ele atribui um endereço fixo (52: 54: 00: 12: 34: 56) a cada NIC. Se você iniciar mais de um convidado no mesmo host, todos receberão o mesmo endereço fixo. Você pode até ver isso nas saídas do ifconfig na minha pergunta original. Naturalmente, isso é um problema se você reunir os convidados juntos, já que é o mesmo que ter duas máquinas físicas com o mesmo endereço MAC na mesma rede. O ARP faz o seu melhor e vai e volta entre eles, mas com longos tempos de espera, me dando os resultados que eu estava vendo.
Portanto, a solução é adicionar sinalizadores "macaddr = ..." ao parâmetro -net para cada convidado, de modo que cada um tenha um endereço MAC exclusivo. Exemplo:
# qemu-kvm -hda <disk-image1> -m 2048 -vga std -vnc :3 -net nic,vlan=0,macaddr=52:54:00:00:00:03 -net tap,vlan=0,ifname=tap0,script=/etc/qemu-ifup
# qemu-kvm -hda <disk-image2> -m 2048 -vga std -vnc :4 -net nic,vlan=0,macaddr=52:54:00:00:00:04 -net tap,vlan=0,ifname=tap1,script=/etc/qemu-ifup
Na minha opinião, o comportamento padrão do qemu deve ser mais inteligente sobre isso, mas suponho que é bastante importante que cada convidado receba o mesmo endereço MAC toda vez que for iniciado, independentemente da ordem em que foi iniciado. Talvez os autores não pudessem. Pense em uma maneira de garantir isso.
Independentemente disso, se você estiver executando vários convidados na mesma rede (virtual ou não), certifique-se de definir o endereço MAC de forma explícita e exclusiva. Caso contrário, você terá o mesmo problema.