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="nomodeset text"
...
GRUB_TERMINAL=console
Regenerate the grub config: sudo update-grub2
After that Ubuntu Server just boots fine in headless mode without any HDMI cable plugged in.
(updated 2024/06 for proxmox: "nomodeset text")
ref: https://bbs.archlinux.org/viewtopic.php?id=233260