Network security rule lost efficiency after VM recreation

Question

I have a Network Interface with 2 inbound rules.

1. Allow ssh from my working station to the NIC on port 22. (AllowSSHRule) -------- Priority 100
2. Deny all inbound connection from any cidr on any port to any cidr on any port. (DenyAllInboundRule) ---------- Priority 1000

Then I create a virtual machine with the NIC attached. Everything works well. I can successfully ssh into the machine. But I fails to ssh into the machine after I delete the old machine and created a new one. I verified that's because the DenyAllInboundRule was preventing the connection.

The way to reproduce. (It's not guaranteed that this can be reproduced everytime. It's kind of flaky behavior)

1. Create VM and wait for creation to complete. Succeed to ssh into VM.
2. Delete old VM and wait for deletion to complete
3. Create new VM with the old NIC, old data disk, old SSH key, etc...
4. Wait for new VM creation to complete and try to ssh into VM. -------- Failed to ssh.
5. Delete the DenyAllInboundRule and try to ssh into VM. ----------- Succeeded to ssh.

I think there might be a possible reason:

1. When deleting the old VM, the NIC somehow was not fully attached to the VM. (Although I verified that the NIC was attached to the VM through Azure protal and az vm instance view)