Some further diagnostics. I tried to ping yahoo.com from VE and ran this on the HN:
tcpdump -nni venet0
tcpdump: WARNING: arptype 65535 not supported by libpcap - falling back to cooked socket
tcpdump: WARNING: venet0: no IPv4 address assigned
tcpdump: verbose output suppressed, use -v or -vv for full protocol decode
listening on venet0, link-type LINUX_SLL (Linux cooked), capture size 96 bytes
15:27:14.805958 IP X.Y.152.160.32849 > 128.107.241.185.53: 28376+ AAAA? vps8.domain.com. (38)
15:27:19.804752 IP X.Y.152.160.32850 > 192.135.250.69.53: 28376+ AAAA? vps8.domain.com. (38)
15:27:23.712328 IP X.Y.152.160.32851 > 128.107.241.185.53: 63647+ A? yahoo.com. (27)
15:27:24.804681 IP X.Y.152.160.32849 > 128.107.241.185.53: 28376+ AAAA? vps8.domain.com. (38)
15:27:28.711669 IP X.Y.152.160.32852 > 192.135.250.69.53: 63647+ A? yahoo.com. (27)