Normally if they are in the Call Reoute forms it will warn you and you can't delete it.
Although the HG may be call rerouted for some reason, because you have deleted it you won't know.
Regarding searching for free dn's, if you have a 2 digit DN it will not show when searching longer digits as you saw.
e.g. if there is a FAC or any DN of 55 it will not show anything that is longer as it will be considered in use. 55, 55x, 55xxx, 55xxxx etc...