The main problem here being that scaleway uses cloud-init, which then uses netplan, which then sets up systemd-resolved incorrectly because netplan only supports a few parameters to setup the connection.

Edit the netplan and tell it to not use the DHCP provided DNS servers

vim /etc/netplan/50-cloud-init.yaml

 ...
 dhcp4: true
 dhcp4-overrides:
   use-dns: false
 dhcp6-overrides:
   use-dns: false
 ...

Now set systemd-resolved to use specific DNS server for all interfaces Here I am using a public DNS64+NAT64 resolver from nat64.dk - you can find more at nat64.net

vim /etc/systemd/resolved.conf

...
[Resolve]
DNS=2a00:1098:2b::1#dot.nat64.dk
DNSOverTLS=yes
...

Setup Debian 12 on a Scaleway IPv6 only instance to use DNS-over-TLS

reboot