Are you using an extension like TACO that creates opt-out cookies?

If clearing the cookies doesn't help then it is possible that the file cookies.sqlite that stores the cookies is corrupted.

Rename (or delete) cookies.sqlite (cookies.sqlite.old) and delete cookies.sqlite-journal and cookies.txt, if they exist, in the Profile Folder in case the file cookies.sqlite got corrupted.

The cookies are still there after doing what you describe. Should I restart Firefox after deleting the folders?

There are 2 files "action.js" and "view.js" which do seem to be opt-out extensions

Thanks

If you have an extension that adds such opt-out cookies then you can't remove those cookies unless you uninstall that extension. Having those opt-out cookies permanently is the purpose of such an extension.