Just wondering if anyone can explain why when I delete all browsing data using, for example, Firefox, then when I run CCleaner it finds Firefox browsing data like cookies and cache that need to be removed. I thought browsers were supposed to remove all this data. Is this normal (as well as quite annoying)?
Yes it's normal.
Although browsers will delete most cookies and your browsing history, if you set them to, they will usually leave some things behind by design.
"Persistent" cookies (supercookies), session checkpoints, cache, etc. can be left behind and not cleared by the browser - as can things like old crash reports and so on.
For example; when I was writing my own batch cleaning routine for Firefox I found that cookies/supercookies were stored if 4 different file locations, the cache/activity stream in 3 locations, crash reports in 2, and the session checkpoints in another.
That will be partly so that they can pick which ones they clear and which ones they don't when you run the browsers own cleaning routing.
If you have multiple users on your computer then each user will have their own copy of each of those files.