RockGrid is perfect for such scenarios:
You get nice, condensed, sortable, paginated tables
You can style cells easily (like statuses for sent, pending, draft etc)
You have a batcher built in, making it possible to send x mails at a time, running via AJAX so you don't get server timeouts
The main reason why I released it under the MIT license was that it can be built into other modules easily.
That would be a process module and MarkupAdminDataTable and LOTS of custom code...