I'd give you another $20 if you added a TiVo-like "Deleted Items" folder. It wouldn't be too difficult- when 'deleting' a show in your UI, don't do anything but mark the video in your db as deleted (with the date deleted), then monitor the drive for disk usage. Once it hits a few GB below the Media Center's configured max size, purge the least recently deleted shows until there's enough space again. Then add a new column for the deleted shows, and allow playing from there or undelete.
Obviously, if someone deletes a show by other means it wouldn't be recoverable, but since I (and I suspect others) only delete shows from the RTVHD interface, this could work.