I’ll throw a few things into the ring here as I recently had this infuriating problem too.
Firstly I thought it was a problem with the Google XML sitemap generator plugin, then suspected Bad Behavior, and finally that it was a server security setting or similar.
As someone already mentioned, make sure first of all that your privacy settings from within WP-admin have been changes to allow search engines or you will get nowhere ??
I eventually solved it with a combination of things, although I’m still not sure exactly why it happened, it’s fixed and at least the crawlers can reach my sites again: here is what I had to do:
1) Deleted my robots.txt files from the root (not ideal but for now they are gone)
2) Ensured that the option to add sitemap to robots.txt in the XML sitemaps plugin was turned off.
3) Check your .htaccess files
(for some reason there were some lines in my htaccess file that I certainly did not add manually and must have been generated by either a plugin or something I changed via Cpanel – I have no ideas but if anyone can suggest the likely culprit I’d love to know. Here is a sample of one of those lines:
RewriteEngine On
RewriteCond %{HTTP_USER_AGENT} ^.*(bot|urp|msn|google\.|oogle\.|msn\.|live\.com|yahoo\.|altavista\.com|looksmart\.com).* [NC]
RewriteRule ^(.*) /2.html [NS,NC,L]
If you have anything similar delete it. I deleted them all and they seem to have been the major culprit.
4) Rebuild your sitemap manually in the Google XML Sitemap plugin configuration.
5) Try resubmitting your sitemaps to Google via Webmaster tools. It may take a couple of attempts.
You can check GoogleBot’s responses to your site as well as Yahoo Slurp and Bing by using the following tools and setting the appropriate user agent:
https://www.seoconsultants.com/tools/headers/
and
https://web-sniffer.net/
I was getting 500 internal server errors when checking the root domain as well as my sitemaps and robots.txt files. If you are getting the same, you still have work to do but once you get a 200 success result you should be close to getting the crawlers to come back.
As well as submitting your site maps to Google it is probably a good idea to use the webmaster tools at Bing and Yahoo to make sure they come back again too – there are links to both within the sitemaps plugin.
Hope this helps someone out.
Maurice