Deleting Record with ExternalID Dosent delete internally

Deleting Record with ExternalID Dosent delete internally

I deleted the record containing ExternalID 
But when I add the record again with same external ID it gives error

Response {"data":[{"code":"DUPLICATE_DATA","details":{"api_name":"Code","id":"4342876000009687028"},"message":"duplicate data","status":"error"}]}

I am using this to post
https://www.zoho.com/crm/developer/docs/api/v2/insert-records-ext.html

Also when I call the Get Record with External ID it does not gives me record back so externalID's are stored somewhere else and are creating issues.