Eu encontrei a seguinte solução. Ainda estou aberto a boas alternativas e sugestões.
Em cada host Xen:
echo 1 > /proc/sys/net/ipv4/ip_forward
iptables -t nat -A POSTROUTING -m physdev --physdev-in vif5.0 -o eth0 \
-j SNAT --to-source 3.3.3.71
Em cada domU tendo um IP privado (10.0.2. *):
route add -net 3.3.3.0 netmask 255.255.255.0 dev eth0
route add default gw 3.3.3.71
route del default gw 10.0.2.1