Podrias detallar un poco mas el problema, ya que no entiendo de donde sacas un nodo inexistente

?
Mas alla de mi duda, podrias probar el try...catch, es decir, mas o menos asi:
bool borado = true;
try
{
//Borrar nodo
......
}
catch
{
//Hay un error al borrar, posiblemente el nodo no existe
borado = false;
}
if(borrado) //El nodo se boro
else //El nodo no existe
Bueno, creo eso te puede servir, aunque la verdad no comprendo de donde sale ese nodo inexistente. Saludos.