Try moving it first then deleting it (works on some patchs in 2000) or use RDO or CDO to do the job for you (you will have to install them)
Set objDeletedItem = objDeletedItem.Move(DeletedFolder)
objDeletedItem.Delete
CDO way
Set objCDOSession = CreateObject("MAPI.Session")
objCDOSession.Logon "", "", False, False
Set objMail = objCDOSession.GetMessage(objItem.EntryID, objItem.Parent.StoreID)
objMail.Delete
RDO
set objRDOSession = CreateObject("Redemption.RDOSession")
objCDOSession.Logon
set objMail = objRDOSession.GetMessageFromID(objItem.EntryID>)
objMail.Delete
You could also mark the message first before you delete it and the loop through the deleted items folder and find it an dthe call delete a second time. Mark it using a Userproperty.
objMail.UserProperties.Add "Deleted", olText
objMail.Save
objMail.Delete
loop through you deleted items look for that userprop
Set objDeletedFolder = myNameSpace.GetDefaultFolder(olFolderDeletedItems)
For Each objItem In objDeletedFolder.Items
Set objProperty = objItem.UserProperties.Find("Deleted")
If TypeName(objProperty) <> "Nothing" Then
objItem.Delete
End If
Next