1. You can actually have multiple Apple IDs. The email address has to be unique, there is nothing preventing you from creating a different Apple ID so long as your email address is unique (not currently being used).
2. iCloud can use an entirely different email address than your Apple ID. You can always sign into iCloud using your Apple ID. You can't however log in to Apple support using an iCloud ID that isn't the same as your Apple ID.
3. iCloud is always ON unless you exit out of it (you know, turn off Find My Mac and all that stuff). As such, whenever you activate a new device, it remembers information about you and transfers it to your new device.
It's that seamlessness that causes it to sometimes remember information that is no longer current. As such, you should always completely log out of iCloud before changing your Apple ID. Because it will continue to use the old credentials that you are logged in with iCloud even if your Apple ID is now changed.
Have you tried logging out of iCloud on all of your devices and then relog back in using your new Apple ID credentials? This also applies to iTunes/App Store. Those pesky services people are usually always logging in to their accounts on 24/7 without even realizing it. Any one of them will cause outdated email addresses to remain alive until completely logged out and back in again.
Privacy is a subjective term. As soon as you put anything out on the internet, it's out there forever. You may not be able to find it but some server out there has it stored somewhere. The iCloud is "out there." True privacy is not having any internet presence whatsoever. But that ship as sailed.
