When you tried to delete it via Safari prefs was the item with which you were left identified as "Cookie" or "Local Storage"?
It was listed under the Cookies heading, not the Databases.
So you're saying that those cookies that you couldn't delete in Safari were actually listed as cookies in your Cookie.app pane?
Very frequently, cookies that I delete from Prefs > Privacy > Manage Website Data... reappear in the same pane...identified as "Local Storage", NOT "Cookie", but I don't recall ever running into that situation.