"I hope I'm not beating up a straw man here, but I have seen many claim that REST is a good solution that scales well because the web is built on the REST philosophy. The principles of REST are why the web is a success, and so if we use REST, we can attain the same benefits."
I don't think this is correct. REST piggybacks on the web's architecture, but I wouldn't say that the web is built on the REST philosophy, in part because REST postdates the web's initial growth. The web was a success almost in spite of itself, but REST wins by cherry-picking the good bits.
"If this is the case, is there any good example of REST?"
There is an interesting discussion of this and HATEOAS here: http://www.suryasuravarapu.com/2009/03/restful-api-and-hateo.... The examples given are Amazon S3 and the NetFlix API.
"The only examples I know of where HATEOAS is satisfied are HTML forms, as I mentioned, Atom feeds, and OpenSearchDescription."
A plain GET link can be an embodiment of HATEOAS. Remember, it's application state, not resource state that's key here.
"I think HTML forms are a perfect example of REST, since they supply the client with all necessary information to build the next request, and URLs do not need to be constructed manually."
Some are, some aren't. It depends what HTTP method you're using and what the server does with the request that makes it RESTful (or not). From that perspective, plain links are just as RESTful as forms - provided they're treated correctly.
"The way 302s are used to redirect to the newly-created resource makes web browsers behave more RESTfully, since they prevent reloads from resubmitting POST requests"
Preventing resubmissions is more about interface design than REST, though. From REST's point of view it's not wrong to repeat a POST. I'd argue that strictly speaking either a 201 or a 302 might be correct, depending on what you're POSTing. If you've just POSTed to a collection URI, then a 201 response with a list of collection member resources would be just as correct as a 302 with the address of the newly created resource. The latter is more conventional, but as I say, that's a UI concern, not because one is more RESTful than the other. There are other ways to protect the server from resubmission problems, but they involve more work for the developer.
If you're PUTting, I'd argue that a 201 should always be correct, but given that browsers don't support PUTs directly anyway, that's not relevant here.
"All I'm trying to do is show that there are at least two codes, 201 and 302, that properly RESTful services might return, to support my argument that response codes are not uniform across all REST services."
I hope I've shown that it's not in any way inconsistent to support both.