I'm confused as to how apt works - apparently, after issuing apt update, the update-command-not-found works as expected. Yet, I had already installed quite a few packages before issuing apt update, so I thought the package listing was already downloaded..?

command-not-found relies on apt-file for the database, apt-file relies on apt (it provides an apt configuration snippet to instruct it to download Contents files).

So yes an "apt update" is needed before "update-command-not-found" does anything useful.