I hypothesize that part of the reason a full REST(w/HATEOAS) isn't popular (maybe "popular" isn't the right word here. maybe "pervasive"?) is the increase in work to move from a Type-I to a REST interface [1]. This is not insignificant in terms of up front costs. Longer term being more restful might indeed ease refactoring and versioning, but by then you may have more help working on the api (after growth). In addition then is of course down the road and things fall by the wayside.

When I try to think of some of the nicest APIs I have actually used, I don't recall them being 100% REST compliant.

I am still not sold on putting versioning in the headers. Url based versioning has the benefit that the version being used is readily apparent (visible), as well as easing scalability due to the ability of frontend proxies to route based on url partials. The pragmatist in me says url versions are 'ok'. Maybe not the best, but as a trade-off "good enough" if it makes implementing them easier.

[1]: http://nordsc.com/ext/classification_of_http_based_apis.html