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.
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 allows you no other option for cloud 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.