For SEO purposes is a bad idea to have 2 sites heavily interlinked. You could be penalized by Search Engines. IMO you should have only one site with different URLs for both versions: AJAX and NOT-AJAX. Probably, the Ajax page won't be high ranked because their poor on-page factors. I was using that method for several years, and my non-ajax pages has been high ranked on Google.
No, that's not cloaking. Definition on cloaking on wikipedia: "Cloaking is a black hat search engine optimization (SEO) technique in which the content presented to the search engine spider is different from that presented to the users' browser. This is done by delivering content based on the IP addresses or the User-Agent HTTP header of the user requesting the page...."
Yes, the izwanmad suggestion is cloaking. I simply said that my suggestion (different URLs on same site for both versions) is not cloaking.
Just use AJAX as candy to your site. Build the site using HTML and CSS and then add AJAX effects. If you use javascript you should always use the <noscript> code anyway - it's good for accessibility and search engines (SE's read noscipt coding)
yepp - the easiest way out - is using ajax as a nice and beautiful addition to something already existing