R – Stateful Web Services

One word: Don't.

OK obviously that isn't a real answer. But still SOAP should be avoided at all costs. ;-) Is it possible to add a proxy server between the iPhone and the web service? Perhaps something that converts REST into SOAP for you?

You could try CSOAP, a SOAP library that depends on libxml2 (which is included in the iPhone SDK).

I've written my own SOAP framework for OSX. However it is not actively maintained and will require some time to port to the iPhone (you'll need to replace NSXML with TouchXML for a start)

While it's only a small difference but it should still be mentioned:

It's not state in web services that kill scalability, rather it's state on the App Server that's hosting the web services that will kill scalability. The moment you say that this user needs to access this server (as done in sticky sessions) you are effectively limiting your scalability options. The point you want to get to is that 'Any of your free load-balanced App servers' can handle this web service request and if I add 1 more App Server I should be able to handle % more users.

It's totally fine (and personally recommended) if you want to maintain state to pass in an authentication token and on each request get the service to retrieve your 'state' from a data store (preferably a redundant and partitioned one, e.g. distributed+replicated key/value data store). That's how Amazon does it with SimpleDb and Google with BigTable.

Ebay takes a slightly different approach and stores most of the clients state in a cookie so it gets passed in with every request. Although it generates a lot more traffic, it still scalable as any of their servers can still handle the request.

If you want a scalable data store I would recommend looking at redis it has speed and features that can't be beat in a key/value data store.

You should also check out highscalability.com if you want access to good material on how to build fast and scalable services.