During the summer, we temporarily returned 403 responses to nearly all bot user agents because of capacity problems. Googlebot was included in that block for more than a month. After fixing the capacity issues and allowing Googlebot again, Search Console reported that most of our pages were not indexed because they returned 403 responses.
We used the "Validate fix" option, but there has been no visible progress for more than six weeks. Requesting indexing for individual URLs works, but there are nearly one million pages to recover. The pages are mostly long-lived, although URLs are added and removed regularly.
We currently do not have a sitemap because the site had previously been indexed well without one. Would generating and submitting multiple up-to-date sitemaps be the best way to speed up reindexing, and are there any other steps we should take?
3 Answers
For roughly a million URLs, generating sitemaps should be the first recovery step. Individual URL inspection requests are meant for a small number of pages, while sitemaps give Google a scalable list of URLs to crawl. You can split the URLs across multiple sitemap files and submit them through a sitemap index. I also wouldn’t wait for the validation process to finish—validation confirms that the 403 problem is gone, but it isn’t a bulk reindexing request.
The 403 responses are the main historical problem here, so make sure the important URLs now return successful responses consistently to Googlebot and that there are no capacity limits, intermittent errors, or accidental blocks. A 404 is appropriate only when a page is genuinely gone; it shouldn’t be used as a replacement for a temporary access block.
Submit a sitemap even if the site previously performed well without one. A similar large-scale recovery started moving within a day after a sitemap was generated and submitted. If the site uses a common CMS, a sitemap extension can automate updates; otherwise, create a sitemap index with regularly refreshed files containing the current canonical URLs.

That matches my experience too. Once the sitemap was submitted, crawling picked up much more quickly.