Alternativa ao que adonis sugeriu no comentário, você poderia fornecer o caminho completo para a máquina virtual como argumento para o comando VirtualBox
. Em outras palavras, a linha exec, para minha 15.10 Ubuntu VM, poderia ser assim:
Exec=VirtualBox "/home/Serg/VirtualBox VMs/Ubuntu 15.10/Ubuntu 15.10.vbox"