Eu poderia encontrar meu Headless VB com a combinação dos seguintes comandos:
# Update arp table
for i in {1..254}; do ping -c 1 192.168.178.$i & done
# Find vm name
VBoxManage list runningvms
# Find MAC: subsitute vmname with your vm's name
VBoxManage showvminfo vmname
# Find IP: substitute vname-mac-addr with your vm's mac address in ':' notation
arp -a | grep vmname-mac-addr
Mas ainda mais fácil: no linux, você pode se conectar ao VB:
# Default VirtualBox Listening Port: 3389
rdesktop -N hostingserver:3389
Este comando irá abrir uma janela shell, e você terá acesso direto ao Headless VB, onde você pode recuperar seu Headless VB IP: ip addr