Doing a show running-config inside vtysh after a reboot can either have just has a single (incorrect) hostname line of 'debian', or TWO hostname lines of 'debian' and then the correct hostname.
The domainname inside frr very rarely set. I suspect this is because dns-domain-name is set at priority 400, but the bootstrap of frr is at priority 150
https://github.com/vyos/vyos-1x/blob/current/interface-definitions/dns-domain-name.xml.in
https://github.com/vyos/vyos-1x/blob/current/interface-definitions/system-frr.xml.in
This leads to a non-deterministic startup where sometimes the hostname is set, and imported into frr correctly, and some times it's not.
This is most visible on a single CPU VM, which makes issues like this stand out, as two things can't happen at the same time.
I suspect a simple fix for this would be to set the system hostname and domainname earlier than priority 150.