The AJAX approach to Web apps does provide a genuine user interface benefit. A full page load is very disruptive to application flow, and being able to have new data appear without incurring that penalty is great. Most of the time you only need to load a little bit of data anyway, and it's wasteful to reload all the markup that wraps it.
AJAX solves that problem, but it creates the new problem that your address field no longer properly reflects the navigation you do inside a web app. #! URLs are one approach to fixing it, and pushState will do even better. At that point, the user won't even have to notice that the Web app they use is built in an AJAXy style, other than the navigation being smoother and faster.
On many examples I don't see any real disruption to application flow with just using normal links, though there are more full-fledged webapps (like gmail) where I would agree. Playing around with old v. new Twitter, the old one actually has considerably faster navigation performance, at least on my setup (and I'm using a recent Chrome on a recent Macbook Pro). Sure, some HTML header/footer stuff is being retransmitted, but it's not very big.
Within an app, my current context (which control has the focus etc) is important and a full page reload loses all of that.
Within a web site, as it is less interactive, this stuff doesn't matter so much.
As to whether New Twitter is a site or an app is debatable (I say site and therefore shouldn't be using #!). And as for Gawker...
Not every website is a web app. Just show one article or item or whatever the site is about under one URI.
Apart from not being supported in IE - the browsers that do support it still have quirks e.g. your code has to manually track scroll state.
And your server could easily send a fully rendered page on the first page load when it receives a full URL (one which was made by pushState and linked elsewhere) and still subsequently load pages via XHR. So it wouldn't have to parse any JS on first load -- subsequent loads would, but they'd be saving time from not downloading as much and not refreshing the entire page.
See <http://dev.w3.org/html5/spec/Overview.html#dom-history-pushs...; for spec details.
It's in Safari, Chrome and Firefox. While Opera and IE don't have it yet, it would be easy to use conditionally on browsers that support it. I'm a little surprised that more sites don't use it.
EDIT: This chart shows what browsers it will work in: http://caniuse.com/history