Re: the meaning of stateless

This has been a really insightful thread.  Thank you Brian for starting it.

After 7 years of trying to fully understand REST I'm still discovering nuances that are not clear, such as "the meaning of stateless."  If I were better at understanding abstract explanations[1] I would probably be much farther along but I'm just no good without a lot of relevant examples that illustrate the associated principles.

To that end I'd like to ask about some examples?

1.) Shopping cart:  We have a web API that allows a user to add items and the server keeps track of the items in my shopping cart. For example a shopper would first add items to their shopping cart which behind the scenes would POST to a "new cart" resource, (B 1..n) POST to a "new item" resource for each item to be purchased, (C, D) PUT billing and shipping addresses to the cart, (E) PUT payment information and finally (F) PUT a "order-placed" value to the cart to place the order.

2.) Batch Operations: In "RESTful Web Services"[2] in the section[3] preceded a few pages by the section "Why Stateless Matters"[4] they recommend to use "Batch Operations" for transactions such as the archetypical "move funds between checking and savings accounts" example.  Specifically they suggest (A) POSTing to get an account transfer transaction ID, (B 1..n) PUTting the new balances to the different accounts, and then (C) PUTting to the account transfer transaction ID to complete the transaction. And they make no mention of this approach being stateful after just writing about statelessness.

Are these examples stateless, or not? Are they RESTful, even if they use resources and hypermedia, et. al.?  If they are not RESTful then does that mean they are doing it wrong from a use-case perspective or that RESTfulness needs to be evaluated like other criteria, i.e. performance, ease of development, et. al?

-Mike 
[1] http://www.ics.uci.edu/~fielding/pubs/dissertation/net_arch_styles.htm
[2] First Edition, Richardson & Ruby 
[3] Page 230
[4] Page 222