CVSTrac includes a powerful repository browser. It allows you to quickly navigate through the repository (deleted or otherwise) and view the change history for any given file.
The basic browser view is simply a list of filenames. Directories are always listed first. Clicking on a file takes you to the file history page.
More recently added, the Long view is similar to that provided by applications like cvsweb. Files are listed in a table with revision, user, age and check-in comments. Clicking on the column headers causes the display to be sorted according to the column.
The browser shows deleted files with a red 'X' icon. Because of how CVS does branches, this deleted state only reflects the most recent commit for that file in any branch. It may (and probably is) still be an active file somewhere in the revision tree.