To assist in determining the reason why this occurred, run a Dtrace of EVPlaceholderService on the File server and then delete a placeholder. 
If the Dtrace shows the following, verify that the policy being applied to the Volume/Folder is set to Delete archived file when placeholder is deleted

(EVPlaceholderService) <1608> EV:M [EvFileDeleted] Discarding a delete vault item request for deleted file: C:\Test Folder\Test.docx as the delete from Vault flag is false

1. Open the Vault Admin Console, expand Policies | File | and click Volume or Folder
2. Go to the Properties of the Policy (either volume or folder)
3. On the Shortcuts tab, verify Delete archived file when placeholder is deleted is enabled.

Note: Prior to EV 8.0 sp2, any file that was archived before the DOD policy was set will still be flagged as false. The flag will remain as false until the file is recalled, and deleted from the archive manually.

Post EV 8.0sp2 forward, DOD is now retroactive. This means, if a placeholder is deleted before the option is enabled, the placeholder can be recreated using the FSA utility, the option can then be enabled, and the placeholder that was recreated can then be deleted and the associated file in the archive will also be removed. 

To verify if a placeholder delete from Vault flag is false, run the following command:

FSUtil reparsepoint query \\fileserver\folder\targetfile.extension

The command should show the following:

C:\>fsutil reparsepoint query "C:\Test Folder\test.docx"
Reparse Tag Value : 0x00000010
GUID : {9DD58ACD-4BE7-4F36-9CE3-B7738EE3C702}

Reparse Data Length: 0x00000840
Reparse Data:
0000:  61 1e 00 00 45 00 2d 00  56 00 41 00 55 00 4c 00  a...E.-.V.A.U.L.
0010:  54 00 30 00 31 00 32 00  33 00 34 00 35 00 36 00  T.0.1.2.3.4.5.6.
0020:  37 00 38 00 00 00 00 00  97 26 00 00 00 00 00 00  7.8......&......
0030:  00 00 01 00 00 00 00 00  01 01 00 00 68 00 74 00  ............h.t.
0040:  74 00 70 00 3a 00 2f 00  2f 00 76 00 61 00 75 00  t.p.:././.v.a.u.
0050:  6c 00 74 00 31 00 2f 00  45 00 6e 00 74 00 65 00  l.t.1./.E.n.t.e.
0060:  72 00 70 00 72 00 69 00  73 00 65 00 56 00 61 00  r.p.r.i.s.e.V.a.
0070:  75 00 6c 00 74 00 2f 00  64 00 6f 00 77 00 6e 00  u.l.t./.d.o.w.n.
0080:  6c 00 6f 00 61 00 64 00  2e 00 61 00 73 00 70 00  l.o.a.d...a.s.p.

The flag for delete from vault on delete is located on the third data line:

0030:  00 00 01 00 00 00 00 00  01 01 00 00 68 00 74 00  ............h.t.

00 = Delete from Vault and delete on recall are both false
01 = Delete from Vault is true. Delete on recall is False
02 = Delete from Vault is false. Delete on recall is true
03 = Delete from Vault and delete on recall are both true

If the Dtrace shows the following, verify that the file server target is set to allow deletes:

(EvPlaceholderService) <3940> EV:M The file: \\?\C:\Test Folder\Test.docx will NOT have its corresponding archived item deleted from the Vault as either the File server is in passive mode or the file is contained in one of the restore folders.

1. Open the Vault Admin Console and expand Targets then File Servers.
2. Right-click the file server in question and click Properties.
3. On the Properties page, go to the Delete/Recall Placeholder tab. (Figure 1)

Figure 1
 

4. Choose the Delete archived file option.

Note: The safety folders section is intended so that specific sub folders can be added to ignore the delete on delete policy.

ADDITIONAL INFORMATION

If Delete Archived File (Target | File Server | Select Server Right Click Properties | Deleted/Recall place holder tab | Delete Archived File ) is checked, then settings will be applicable for whole File server's Volumes and folder where the FSA Policies are configured for Delete archived file when placeholder is deleted.