I gave up on trying to get "Deleted Object" info with VBScript and figured out (the basics) on how to get AD Deleted Object info using Powershell. 

Thought you might be interested. 

Note, I still prefer VBScript over Powershell but I'm finding there are some things you just can't do with VBScript, so it's nice to know that Powershell may be capable of accomplishing those tasks.

I'm still working on fine tuning this code and researching some performance issues.  If I can get all of this performing well I may put together a Scripting Pro VIP article on this.  Currently I'm finding that Powershell used in this fashion with Excel is very slow.  So heads up on that.

Let me know if you think you'd be interested in reading more about this.  PS, you have to be an Administrator to access this info.

Here's the down and dirty Powershell code:

$dom = [System.DirectoryServices.ActiveDirectory.Domain]::GetCurrentDomain()
$root = $dom.GetDirectoryEntry()
$root.psbase.AuthenticationType=[System.DirectoryServices.AuthenticationTypes]::FastBind
$root.psbase.path ="LDAP://cn=Deleted Objects," + $root.distinguishedname
$search = [System.DirectoryServices.DirectorySearcher]$root
$search.Filter = "(isDeleted=TRUE)"
$search.tombstone = $true
$search.SearchScope = [System.DirectoryServices.SearchScope]::OneLevel
$result = $search.Findall()
#$result

$x = New-Object -comobject Excel.Application
$x.Visible = $True
$y = $x.Workbooks.Add()
$z = $y.Worksheets.Item(1)
$row = 1
for ($a = 0; $a -le $result.count; $a++) {
$z.Cells.Item($row,1) = $($result[$a].properties.distinguishedname)
$z.Cells.Item($row,2) = $($result[$a].properties.dscorepropagationdata)
$z.Cells.Item($row,3) = "$($result[$a].properties.objectsid)"
$z.Cells.Item($row,4) = $($result[$a].properties.whencreated)
$z.Cells.Item($row,5) = $($result[$a].properties.samaccountname)
$z.Cells.Item($row,6) = $($result[$a].properties.name)
$z.Cells.Item($row,7) = $($result[$a].properties.usnchanged)
$z.Cells.Item($row,8) = $($result[$a].properties.isdeleted)
$z.Cells.Item($row,9) = $($result[$a].properties.instancetype)
$z.Cells.Item($row,10) = "$($result[$a].properties.objectguid)"
$z.Cells.Item($row,11) = $($result[$a].properties.cn)
$z.Cells.Item($row,12) = $($result[$a].properties.objectclass)
$z.Cells.Item($row,13) = $($result[$a].properties.usncreated)
$z.Cells.Item($row,14) = $($result[$a].properties.useraccountcontrol)
$z.Cells.Item($row,15) = $($result[$a].properties.lastknownparent)
$z.Cells.Item($row,16) = $($result[$a].properties.whenchanged)
$z.Cells.Item($row,17) = $($result[$a].properties.adspath)
$row++
}
$y.SaveAs("C:\temp\DeletedObjects.xls")