When you place an order in deleted status, there will be a "purge" button that shows. Clicking the purge button will permanently remove the order. Perhaps you, or someone, clicked that button. What we do, is we have created an "Awaiting Payment" status and orders that we are waiting for payment, we move the orders there, until payment is received.