I only discovered, after I deleted a bunch of old labels, that that does not also delete the messages under that label (thanks for having that morsel of info at the bottom of the page rather than anywhere handy, Gmail). How do I now find a huge amount of old messages so I can delete them?
All messages from the deleted label have been archived.
If you do not normally archive messages. You can search for and delete all messages that do not have a label.
Write in the search bar:
-in:Sent -in:Chat -in:Draft -in:Inbox
If you usually archive messages, then I do not find a way to easily delete all messages that were in a deleted label.