I was browsing an eCommerce site and noticed a good use of AJAX. I was on the Product Listing page and when I selected a product rather than opening a new page the Product's Details appeared as an overlay on the same page. Whilst this is great from a usability point of view as far as I'm aware Google can't read AJAX (if this is not the case please let me know!). You might be able to overcome this by creating non-AJAX versions of the pages, however you would likely have to get in the habit of regularly submitting an updated site-map to Google etc.
Yeah ajax is a pain when it comes to seo, the search engines cant read it at all. Like you say, you almost have to have two copies of your site if you had it like that.