Google always has problems with all kinds of different technologies... they use AJAX as well and pretty much made it what it is with their Maps...

I've had a site with a Flash header and Flash ads on the side that got crawled more than a popular blog a friend of mine had... it all depends on alot of things I suppose... I won't worry about AJAX and Google for some projects - or else those projects would never come to life... MSN, Yahoo, etc will still crawl the sites... just make sure you submit to DMOZ.org and you'll get plenty of extra hits :)