Назгулы, находились в Барад-Дуре и покинули крепость вместе с остатками гарнизона, скорее всего, во время боя Саурона на Ородруине.
Цитата:
"he had been straitly besieged in Mordor and all his forces had been destroyed. If any few had escaped, they had fled far to the East with the Ringwraiths".   
"он [Саурон] был плотно осажден в Мордоре и все его силы были уничтожены. Если немногие и уцелели, они бежали далеко на Восток вместе с Призраками Кольца". (UT, "Поражение в Ирисной низине", прим. 20)  Пы.Сы.
Упреждая возможные возражения об "арагорновых штанах". 

1. Почему Назгулы находились в Барад-Дуре, а не на поле боя. 
Неупоминание в хрониках, а также полное молчание непосредственных свидетелей (Элронда в частности) по поводу присутствия Назгулов в сражении  - это очень существенный момент. Так как Назгулы - не рядовые орки или люди, это 
очень заметные личности, с очень специфическими свойствами воздействия на психику. 
Не заметить  этих персонажей на поле боя было попросту невозможно.
2. Почему во время боя Саурона.
Это был самый удобный момент для прорыва к долине Нурна.