My guess is that cron isn't running on your site, or is having problems.
Deletion is done by a background task and task and can take a few minutes.
Note, above, that 'Origin = cli'. That tells you it was the cron task that actually performed the scheduled deletion. This would also account for the recycle bin not working.
For completeness, this is the output from cron too...