I already tried doing a system format of sysNAND, but that didn't help. I did this without the SD and Gateway cards in the console though. I read somewhere update info is also stored on the SD somewhere? Iirc it's the extdata folder, but I'm not entirely sure. Is it safe to just delete that, see if it works?
EDIT: Just tried it by renaming the extdata's sole subfolder. After starting up it gave me the "Creating information on SD" or whatever message again, but going to NNID still gives the "do an update" message. ):