Okay I spent some time investigating this issue and I believe it’s a bug in the Brave Sync Chain mechanism. I grepped through my whole Brave profile directory and investigated all references to the websites for which cookie settings could no longer be deleted.
The only way I found to really fix this issue is to remove all my devices from the current sync chain, then thoroughly clean up the Preferences JSON file in my Profile directory (see below), remove (rm -rf) all the the sync caches (Brave-Browser/Default/Sync Data/LevelDB and Brave-Browser/Default/Service Worker/CacheStorage), and then finally create a new Sync chain and rejoin from all my devices.
I used a RegEx pattern similar to the below to clean up my Preferences file:
%s/((?<=\":\{)|[\,])\"(https:\/\/)?(voice|mail|calendar|docs|drive|world|www)\.(slideshare|hyatt|google)\.(com|net)[^\{]+\{[^\}]+\}[\,]?//g
(Please be careful with your pattern … if you delete just one wrong character, Brave marks the file as “bad” and overwrites most of it. If you’re not into RegEx, you could also try clearing your Site Settings after leaving the Sync chain.)
If you don’t want to recreate your Sync chain for whatever reason, the only other way to work around this issue is to disable the “Settings” synchronization in brave://settings/braveSync/setup before cleaning up the Preferences file as described above. You would no longer have settings synchronization, though.
Good luck.