Okay, I have discovered the answer so may as well put it here for completeness. At the end of /etc/sudoers there is what I thought was just a comment:
#includedir /etc/sudoers.d
However this actually includes the contents of that directory. Inside of which is the file /etc/sudoers.d/90-cloudimg-ubuntu. Which has the expected contents
#ubuntu user is default user in cloud-images.#It needs passwordless sudo functionality.ubuntu ALL=(ALL) NOPASSWD:ALL
So that is where the sudo configuration for the default ubuntu user lives.
You should edit this file using visudo. The following command will let you edit the correct file with visudo.
sudo visudo -f /etc/sudoers.d/90-cloudimg-ubuntu
And add a line like:
user ALL=(ALL) NOPASSWD:ALL
At the end.