My test for immutable Linux servers would be mounting /usr read only for the duration of the host's lifetime. Debian or Ubuntu boxes with unattended upgrades enabled are not immutable.
But you must still apply updates. New immutable images should be created for every package update of the system software. Lots of images, yes, but the point of immutable is to have a known set of packages, that only changes when replaced atomically by another known set on reboot.
When creating new images, install packages and update all to the latest. Disable unattended upgrades. Possibly remove apt altogether. How to accomplish this varies, could be preseed scripting, or post provisioning commands, or something else. Complete all changes to the system before archiving it as an image.
Over in Red Hat land, they have ostree for an atomic upgrade system, and composer aka image builder for image creation in general. Ubuntu possibly has an answer to these.