I think there needs to be a big distinction between web applications (gmail, google maps, online banking) and web sites (msdn, wired,
www.asp.net. AJAX is primarily useful for web applicaitons. AJAX has limited use for web sites.
"The biggest problem with lack of state is that programs, such search engines, can't process AJAX web pages programmatically"
I don't believe that AJAX is actually useful for things that search engines are best at searching. To use the example of MapQuest and Google Maps, I have never searched for London Bridge and had MapQuest come up as a result in a search engine. This although it uses query string parameters to be deterministic it isn't something that is searchable. I can also use the robots.txt to stop search engines and google even tells me how.
"As another example, try using GMail. Click around a bit. Now click the refresh button. Shazam! The page view you had disappears and you return to the Inbox."
This is the same as restarting an application and isn't really a suprise to developers. Sure this may not be the expected user experience, but perhaps the dom standards should give web application developers a way to stop the use of refresh if web apps are to mature.
"Now click the [Back] button. Do you go to the state where you were previously? No! You go back to the prior web page, whatever that was. You cannot go "back" to the prior page in an AJAX site because the browser doesn't manage the state for you"Developers of web application spend a lot of effort and tears trying to remove the problems of back buttons and refresh behaviour. The web browser shouldn't be trying to hold state, although it happens to cache the previous page, as HTML is supposed to be stateless. So if I want to buy into implementing state into a website such as using cookies or hidden fields or fancy frameworks like ASP.NET I don't want the browser interferring with my application state. If I am writing a web site for a company that informs the world on what they do, then I am not keeping any state and the back, forward and refresh buttons hold no fear. Your view is a little simplistic for the variance in reasons for developing for the web.
AJAX maybe abused as it is the new cool feature, but using framesets or domain rewriting can lead to similar problems. I can also use pointers without correctly releasing the memory, but I don't. Any of the technologies developers are presented with can be used in a way that is not best practice. If you do this with an information website such as Wired.Com or MSDN the information will not be found and your business will suffer. I only see this "misuse" of AJAX existing in proof of concept and misinformed developers. Perhaps we should encourage article writers to discuss best practice use of AJAX to help remove your fears.