Deleting a transaction from your wallet does not remove it from the rest of the network.  If it is still floating around out there, your node will get it back from the network and put it back in your wallet.

For best results, you need to unplug your network cable before starting bitcoin after deleting the transaction.  Then you can create a new transaction.  Be absolutely sure that the new transaction uses at least one input used by the old transaction, or you'll end up paying double.