Recently, I had to deal with a Nintex Workflow doing many deletions in a replicated farm by AvePoint Replicator.
On the backup farm, the deleted items where still here.
After discussion with AvePoint engineer, I understood that Replicator use the site recycle bin but the workflow action "Delete Item" use the collection recycle bin.
The solution was to use a lists.asmx web service : UpdateLitItems method with the Delete command.