FWIW my #1 vote would be for Voicemail to store the messages with a timestamp+uniqueid so that more than one person can process mailbox entries at a time and there's no need for sorting/reindexing the mail folders with all the inherent risk that entails (the Current 1.4 app_voicemail gets this horribly wrong; if multiple people access the same mailbox it <b>will</b> lose messages and crash out).
Secondly, Voicemail needs better integration with AGI/FastAGI so that GUI's can manipulate the messages (list, select folders, move, delete, play through phone etc etc). Some means of generating UserEvents in real time as the mail folders are manipulated would also be useful.
And in the already done dept: stop Comedian Mail actually deleting messages. See: http://bugs.digium.com/view.php?id=10740