iCloud has always been a barely-working pile of shit in my experience, inline with Apple's general degradation when it comes to UX.
Right now my iCloud account claims that my storage is fully used up by messages, except this is after deleting all my messages and confirming they are deleted by resyncing a new phone and making sure the conversations are indeed deleted (as they aren't coming back on the new phone).
For a long time (might still be the case), deleting entries or search history in Maps wouldn't actually delete them on anything but the current machine - logging into a brand new machine would bring back entries that were supposedly deleted years ago.