How to get deleted Contacts via REST Api

I'm a third party developer (and a SugarCrm noob) writing an integration limited to the "stock" REST API (so, I can't add endpoints).

My application needs perform an some ongoing sync of Contacts to drive a directory, which is accomplished by querying for changed contacts every half hour by calling /rest/v10/Contacts?filter=

with a filter like:

[

   {
      "date_modified" : {
         "$gt" : "2016-08-18T13:37:02"
      }
   }
]

The problem I'm having is that I don't get deleted records, and therefore don't know to disable them on my directory.

I understand from the documentation that, when a user deletes a Contact, SugarCRM should be soft deleting records, but they are still not being returned to my application.

I also read that I might need to specify that deleted records should be returned (and that this parameter returns ONLY deleted records, but I'm happy to make two calls instead of one):

[

   {
      "date_modified": {
         "$gt": "2016-08-18T13:37:02"
      },
      "deleted": true
   }

]

But that still returns no records.

The client has the purgeRecords scheduled job turned off and, regardless, I still don't get the record back when attempting to query it within five minutes of the client deleting it.

Explicitly querying for the record with /Contacts/[ContactId] return a 404 (as expected):

{"error":"not_found","error_message":"Could not find record: [ContactId] in module: Contacts"}

Given that the client has the purging of records turned off, am I missing a system setting that is indicating that Contacts should be hard-deleted? If it matters, they are deleting Contacts in the record view.

Thank you in advance and any help would be greatly appreciated,

Marco