I did not try to reproduce your exact situation, but some operations called by cache_clear_all write / remove files from the filesystem. If your filesystem permissions are not correct, then
drush cc all will do all of the database clearing just fine, but will leave the other operations undone.
There are two potential solutions to this:
sudo -u www-data drush cc all
Some folks don't like to use 'sudo' with 'drush', but if you run Drush as the webserver user, the cache-clear should work.
- set the permissions of your webserver files so that the user that you run Drush as can read/write to the filesystem.
I usually make my webserver files owned by a 'www-admin' user in production, and I make them owned by the user I log in as on my development system. I set the group of all files to www-data, and make those that the webserver needs to write to group-writable. This works pretty well for Drush + Drupal access on Drupal 7.