I tried seeing if there were some sort of search that could bring up the emails that had a label applied on a certain date, but I can't seem to find one. There's no "date modified" criteria it seems.

The alternative is to...abandon them. I used labels and filters pretty obsessively in the early days. But then I switched to simply searching for everything I needed, and I haven't labelled anything since then.