A mi entender duplicas las cosas.
En el destructor vas a borrar las dos ramas por separado pero estas funciones terminan apoyándose en Eliminar, que de igual forma vuelve a borrar a la izquierda y a la derecha por sí misma.
Tal vez debería ser al revés, que Eliminar estuviera a un nivel superior y fuera las que llamara a eliminar izquierda y derecha para borrar así el nodo completo.
De igual forma, tal y como lo tienes, solo EliminarRamaIzda y EliminarRamaDcha se encargan de llevar a NULL el puntero pero Eliminar no lo hace. ¿Llega el programa a un punto en que Eliminar pasará sobre un puntero que ya ha sido borrado previamente?