Unless you want your URLs to look like twitter.com/someone#!someone_else, you're going to have to take the multi-step page load at some point when you transition from the HTML version to the AJAXy one.
Not if you use the HTML history API: http://html5demos.com/history
Admittedly, you need a modern browser for that. But you can always present full-page-load HTML to users with older browsers and then provide AJAXy history-ified goodness to everyone else.
You follow a canonical link to the resource, get a real page back, with real links, but js click handlers to enable AJAX-goosed speed for those with javascript enabled? And given that they imply a fallback for those times when javascript fails, aren't they actually better?
And GMail is a bit different than Twitter. It handles inward-facing data; content that no-one particularly wants crawled and wouldn't benefit much from caching.