OK, graças ao Takkat, percebi que, se eu alterar o valor do Exec no meu arquivo da área de trabalho, ele funcionaria perfeitamente.
Aqui está minha entrada antiga do Exec:
Exec=VBoxManage startvm Windows
Aqui está o novo:
Exec=VirtualBox --startvm Windows
Não tenho certeza de qual é a diferença técnica, mas, ei, funciona!