The data that Apple does store is kept for good reason…
Apple fixed the issue with plain text URLs being accessible since iOS 9.3, so for the majority of users the problem hasn’t been an issue for almost a year. And Apple has since fixed the issue server side for the rest of users, according to sources familiar with the situation.
Keeping some of the data around for a certain period of time helps devices that may be out of sync to properly receive changes once coming back online, according to these people. So if you have a device that is offline for an extended period of time, when it powers back up, it will be able to reliably sync iCloud to your current Safari setup and recent changes. As noted in the message on iOS (pictured above) when you clear history for Safari, “history will be cleared from your other devices signed into iCloud.”
It’s also important to note that Safari provides the option to “Clear history” opposed to “deleting”, which could have led to some confusion among Elcomsoft and users regarding how the feature functions behind the scenes.
One of the major advantages that comes with using iCloud in the Apple ecosystem is the ability to have your data go with you wherever you go. It can sync data between devices to create a seamless experience. An obvious example is the ability to start browsing a website on your iPhone, and then continue it on your iPad or Mac. And even for your cleared history, iCloud needs to sometimes store data to make sure everything is in sync across devices reliably.
So to recap, since iOS 9.3 almost a year ago (which the majority of users quickly updated to), Safari has kept the cleared records but stores them so URLs can’t be extracted as plain text. This makes the data cryptic thus not allowing anyone to decipher what exactly the browsing data is. For the small percentage of other users, Apple has recently fixed the issue entirely on iCloud’s servers so URLs are never accessible as plain text after cleared from history.