After some trial and error, I found an easy fix: edit the /etc/default/grub file (sudo nano /etc/default/grub) and modify / uncomment the following entries:
GRUB_CMDLINE_LINUX_DEFAULT=""Regenerate the grub config: sudo update-grub2
...
GRUB_TERMINAL=console
After that Ubuntu Server just boots fine in headless mode without any HDMI cable plugged in.