First, there two different kind of on-demand addresses.
1. Registration, these emails are stored in the password manager
2. Throw away, one time addresses
Second, I maintain a two mail folder method: inbox and archive. Sent mails are put into inbox, too. This makes mail threads a whole. From there they are either purged if spam or moved over to archive.
From here I can answer your question, how I manage all those generated addresses. The folders are indexed. So I am able to find anything (if not encrypted). In particular I can retrieve all my used addresses.
- Startup script that fetches the aliases from DB and modifies a mail client configuration so that all randomly generated addresses are annotated with a short descriptive text indicating to whom the address was issued and makes it so that replying sets the From header to the alias.
This combo works well for me.