I just verified this just now. If you want the unused labels removed immediately without having to wait on your schedule, follow these steps:
Settings > Troubleshooting > Optimize Database
Of course, you will have to remove the label from all media that the label is currently assigned to for this to work.
Hope this helps!
