Wiped all disks for Ubuntu installation, but "macOS Recovery over the Internet" still knows my Wi-Fi password

Your Mac contains forms of storage that are persistent, but not stored on your normal disk drive - it is known as NVRAM (Non-volatile RAM) and PRAM (parameter RAM).

This persistent storage is used by the computer to remember user preferences such as which disk drive to boot from by default, audio volume settings, etc. It also contains the password for your WiFi.

The Internet Recovery mode is able to access this storage to obtain an internet connection to Apple's server for downloading the necessary software.

If you wish to clear this storage, you can do so by holding down Cmd-Opt-P-R and then turning on the Mac - hold them down for half a minute or so.

NOTE: If you have set a firmware password, you'll need to disable this before you can clear the persistent storage.