Каким образом Вы вообще организуете сборку мусора? Как определяется порядок удаления объектов?
Если Вы не используете умные указатели, то крайне рекомендую их использовать. Только при использовании внимательно отнеситесь к другой возможной проблеме — циклические ссылки, а то вообще ничего не будет удаляться;)
Что касается singleton-ов, то раздавайте их в виде умных указателей. Храните их все в одном реестре (как уже посоветовали выше), чтобы в момент удаления все их обнулить и отпустить, так сказать свободное плаванье. Они сами удалятся в правильном порядке за счет использования умных указателей.
Всякие Terminate (или Shutdown) нужны для того, чтобы разорвать возможные циклические ссылки, участниками которых является сам singleton.
Вообще, рекомендую при разработке хоть сколько-то сложных программ (40-50 singleton-ов это уже немало) использовать выделенную сущность kernel, которая при запуске создаст и инициализирует все экземпляры (особенно singleton-ы), а при удалении всех их «отпустит». Важно, что именно «отпустит», а не удалит, т.к. между в мало мальски сложной системе всегда возникают связи, которые простая логика «удаления в обратном порядке» не разорвет корректно. Подсчет ссылок Вам в руки.
Мы такой подход опробовали на весьма и весьма больших системах (тысячи объектов, сотни singleton-ов) — все корректно включается и выключается:)