Após a depuração, encontrei a solução.
A causa deste problema reside no fato de que sob o Ubuntu 16.04 e atualizações mais novas e não-assistidas usa o systemd - não o cron - para agendar as atualizações com um grande atraso aleatório:
/lib/systemd/system/apt-daily.timer
está configurado com
OnCalendar=*-*-* 6,18:00
RandomizedDelaySec=12h
Isso significa que ele será executado duas vezes por dia, às 6:00 e 18:00, com um atraso aleatório de até 12 horas. Como isso nem sempre é aceitável para ambientes de produção, tive que substituir essas configurações.
Para manter os arquivos de configuração do pacote inalterados, defini minha substituição em /etc/systemd/system/apt-daily.timer.d/override.conf
(tive que criar a pasta e o arquivo).
Lá eu defino
[Timer]
OnCalendar=
OnCalendar=06:00
RandomizedDelaySec=1h
para que atualizações autônomas sejam executadas às 6:00 mais um atraso aleatório de até uma hora.
Então eu simplesmente reiniciei o timer com systemctl restart apt-daily.timer
(eventualmente preciso recarregar o daemon).
Atualizações não assistidas agora são executadas em momentos previsíveis novamente!