So I just reread your original post and I realized where the problem lies: the Switch connected to the Internet. It most likely houses a database of updates that is downloaded once you connect online. The process I gave you should have gotten rid of the update though. You can also try running DevMenu because it has an option to clear game updates.
Right, I tried the exact steps, still prompting to update the game or start it. Went into recovery, hit cancel on the update, powered down still shows this (not my video, but that's the message).
Just to make sure it's not some weird sx os bug, I dropped back into ofw, launched my original mario odyssey, told it download, let it get the update. Stop getting the prompt.
Went back into SX OS, other games still complained, mario still fine. So it definitely knows there are updates, so it must have a database of latest versions. It just refuses to clear for me for some reason. I tried devmenu as well, I didn't see any update data for the games, only reset required version, tried that, got a warning about save data incompatiblity, still done that prompt.
I did get the latest updates in nsp format for xenoblade and kirby and installed via sx os, the prompt for both those two is gone now. I tried an earlier update with kirby and it still complained, only once going with the latest (3.0) did it shut up. So it definitely seems like it there is a database of latest version for software downloaded. I just can't seem to make the prompt shoo without actually getting it, whether that's by connecting to wifi and getting from nintendo or installing an .nsp of the update.
Little annoying it won't go away, pain in the ass to update all the games, just to make it shoo.