I've seen a number of times when people don't understand the statelessness of HTTP, and try to put megabytes of data in a cookie-backed session--unable to understand why that doesn't work, etc.
This is especially prevalent in .NET land, where there are mechanisms for storing data in hidden forms and hiding the statelessness away from the user.
Why is that a costly mistake? REST is great but it's not the only way to do web development. Read up on continuations, for example. In fact, this very website is using continuations (check out how paging works) and it doesn't seem like a costly mistake.
