GRE e NAT em geral não se dão bem juntos. Normalmente, você precisa de alguma forma de tecnologia PPTP Passthrough no gateway NAT para que ela funcione. O VirtualBox não tem isso.
Não há motivo algum para que o GRE não funcione em adaptadores de rede internos ou em ponte.
Acabei de criar 2 VMs do FreeBSD * e as vinculei a uma rede interna chamada "intnet". Eu dei a eles dois IP's na faixa 172.16.1.0/24.
Eu então criei uma interface GRE em cada host e configurei o tunelamento para trabalhar entre os dois IPs que acabei de alocar.
As interfaces GRE que eu coloquei na faixa 172.16.2.0/24 (.1 e .2)
Eu posso pingar alegremente entre as duas interfaces GRE.
(* Eu escolhi o FreeBSD como era o que eu tinha que entregar e é muito fácil configurar túneis GRE para testar esse tipo de coisa)