Спасибо Всем!
Проблема с картой сайта и All in One SEO решилась гораздо проще.
В настройках All in One SEO есть пункт, в котором можно ограничить количество записей для одной карты. Было 50000. Поставил 10000. Все заработало. Гугл скушал карту без проблем.