Heh, I feel famous now :)
No, I'm afraid my synthetic backup suggestion wouldn't work. Veritas confirmed to me that you have to create the synthetic backup there & then within a policy.
I have made a few suggestions to Veritas on the enhancement program though, keep your fingers crossed :)
I'm afraid your only option to ensure deleted files are deleted is to take a full backup every day. Synthetic backups mean your backups take less time, but they still use the same storage on your backup media...
I've seen a lot of problems reported here from synthetic backups. If you've got the time you may as well run a full backup each day.
Depending how much you're backing up, disk storage is cheap these days - I'm rebuilding my backup server next week as a 2TB array for just over £2,000.
Ross