I know of two probable causes:
Scenario 1
It is interesting you "are using a third-party MS Dynamics hosting". It probably means you are sharing the CRM Servers with other tenants (CRM organization databases). In these kind of environments problems can occur when plugins have not been designed to be thread-safe.
I have seen plugins that would actually garble data of concurrently processed requests. Sources of these errors can e.g. be autonumbering plugin products, shared by multiple tenants in the same deployment. Autonumbering plugins are typically triggered on the creation of records. It is not impossible your records ended up in another database.
Scenario 2
You have a workflow in your system that is triggered (directly or indirectly) by the creation of your record deleting your record. Asynchronous plugins can actually also be a suspect.
Asynchronous processes run outside the original transaction scope, so your code does not necessarily have to be aware of it.