Los destructores se llaman cuando se hace el respectivo delete tras el new o en efecto, de forma automática para objetos ligados a otros (todo lo que no se haya creado con new) cuando se hace el delete del objeto contenedor.
De todas formas, ¿seguro que quieres tener un iterador como atributo? Lo normal es que tengas un método getIterator() que devuelva el iterador cada vez que lo quieras usar. Los iteradores son de un sólo uso y cuando terminas de hacer lo que sea debes descartarlos. Además, puedes tener problemas si la lista cambia pero no haces un nuevo get del iterador. No sé cuál sería exactamente el comporamiento, pero una de dos: o se te corrompe el iterador, o acabas iterando sólo sobre los elementos existentes en la creación del iterador. Tal y como lo tienes, vaticino punteros nulos everywhere.
Tampoco entiendo muy bien eso de arrayNombres[x]->clear(); ¿Qué es lo que quieres hacer exactamente? Si quieres borrar sólo el contenedor, tienes que hacer delete arrayNombres pero no puedes porque es estático así que se encarga ello sólo cuando destruyes AlmacenaUsuarios. Si lo que quieres es borrar los elementos asociados, tienes que hacer delete arrayNombres[x] para cada elemento x.
El clear se hace sólo sobre arrayNombres. No tiene sentido arrayNombres[x]->clear() sino como mucho arrayNombres->clear(), sobre la lista, no sobre los elementos. Aún así sigue sin tener mucho sentido hacer clear() a la lista cuando la vas a borrar inmediatamente. ¿Para qué quieres vaciar una lista que vas a destruir posteriormente? Destruyes la lista y por tanto da igual que esté vacía o llena, la lista se va a pastar.
Si los objetos para nombres no los tienes referenciados por ningún otro lado, hacer clear() a la lista pero no borrar los elementos es un memory leak como una casa. La memoria asignada a cada uno de los elementos no se destruye en ningún momento, y como has borrado la referencia, no tienes ninguna forma de referenciarlos y por tanto de liberar la memoria, así que se quedan colgando en el limbo del heap de tu programa.
