As you mentioned that your OS VHD still shows connected with deleted VM, you would need to take care that first. You can run the BreakLease.ps1 Powershell script in this forum discussion to remove the lease first and then use the Os disk VHD to create a new OS Image. Finally you can use the new OS image to create your new Virtual machine.
Alternatively if you just want to reuse the same OS disk vhd to create a new virtual machine, you can follow the blog below and look for section at the bottom "To reuse the OS VHD blob to create OS Image" to copy the blocked OS blob into a new blob and then use it: