The fact that this is so unintuitive that I had to explain it and I am only 95% sure I got it right is precisely the problem.
Would be very interested in this.
For Notes, I've migrated to Obsidian since I couldn't find a reliable backup method for Apple Notes.
Messages is tricky - I just screenshot anything important since it's so tightly integrated with Apple's ecosystem. Most of my important conversations happen on WhatsApp anyway, which lets me export anything I need to preserve.
It's also the same way ProtonMail encrypts their email. They have to store the private key for you to be able to use the email on any browser.
Only enabling ADP, disabled by default and unavailable in UK, makes it like you describe.
Of course iCloud backup is itself optional. But Apple gives you and the people you're messaging no other option for cloud backups. ADP actually encrypts your backups, but since it defaults to off your messages are almost certainly still readable by Apple thanks to the keys stored in other peoples' backups.
No, if you do not use “Messages in iCloud” then your iMessage private key does not leave your device.
If the messages were still protected by e2ee with key storage only on your devices then it would specify that in the table. Some other data types like keychain passwords and Memoji are in fact protected by e2ee even when ADP is not enabled, and the table reflects that. Messages do not fall in the category of e2ee without ADP.