You can't do this without some sort of database. At least, not for large mail stores. In order to display a view, you must have a model for it. Searching through every email for every view change would take too long for large mail stores; thus you must index.

That doesn't necessarily mean using an SQL database, though the flexibility would be usefull in this case, IMHO.

To fix your problem, whenever mail is deleted, it needs to be removed from the database. Sounds like it would be good to combine this with a mail client. Otherwise, a periodic re-scan of the mail store is needed to delete old links.

Perhaps storing a hash of each message to ID it and checking to see if it still exists?

There is also the problem of determining what kind of data storage this will look at. Are you wanting to parse mailbox format, Maildir format, or IMAP?

How about a POP3 proxy that indexes all messages as it downloads from the server?

The perltwingular interface could have functions to do deletions and management too, to get rid of spam and junk. Heck, an interface to Spamassassin could help with that.