The goal is, ultimately, restrict access of the web service to authorized users, right? Very easy if you control the web service (if you don’t — wrap it in a web service which you do control).
1) Create a public/private key pair. The private key goes on the web service server, which is put in a dungeon and guarded by a dragon. The public key goes on the phone. If someone is able to read the public key, this is not a problem.
2) Have each copy of the application generate a unique identifier. How you do this is up to you. For example, you could build it into the executable on download (is this possible for iPhone apps)? You could use the phone’s GUID, assuming they have a way of calculating one. You could also redo this per session if you really wanted.
3) Use the public key to encrypt “My unique identifier is $FOO and I approved this message”. Submit that with every request to the web service.
4) The web service decrypts each request, bouncing any which don’t contain a valid identifier. You can do as much or as little work as you want here: keep a whitelist/blacklist, monitor usage on a per-identifier basis and investigate suspicious behavior, etc.
5) Since the unique identifier now never gets sent over the wire, the only way to compromise it is to have physical access to the phone. If they have physical access to the phone, you lose control of any data anywhere on the phone. Always. Can’t be helped. That is why we built the system such that compromising one phone never compromises more than one account.
6) Build business processes to accommodate the need to a) remove access from a user who is abusing it and b) restore access to a user whose phone has been physically compromised (this is going to be very, very infrequent unless the user is the adversary).