A scheduled cron runs as uid 0, the anonymous user, and therefore probably can't delete anything. When you run cron from the admin menu, it uses your current session, so you can delete things.
If you google for "drupal run cron as uid 1" you will see some workarounds. Most involve switching users inside your
hook_cron and then restoring the session when you are done.
What should be possible is to invoke
drush -u XXX cron from your crontab instead of the the typical
wget method. Some searching will dig up the proper way to call it (you need to get the environment and Drupal basedir set right). I would not run as uid 1, though. Pick (or create) a user with sufficient permissions to do what you need.
What would also be possible is to create a script that bootstraps, loads the proper user, and then does your task. Lock this down in your
.htaccess and call it from your crontab.