I'm not looking for a digital wallet, but rather a service with an API that we could use to let people who use our app make payments to others using our app (iOS/Android)
Does this service exist yet?
There are a bunch of them... Paypal has a pretty easy to use one: PayPal Mobile API Also checkout kuapay.com... paypal is your best bet in your case.
Im not aware of anyone offering this, but I would get in contact with Venmo. At the moment, it doesn't look like they offer any APIs; but perhaps they would be open to hearing ideas about P2P payments within 3rd-party apps. As it stands, the service is easy and cheap (no transaction fees) and you can send money via text message or their own iOS/Android/BB apps. They have the functionality you're probably looking for, should be an interesting prospect for them to consider at least.
I am not sure if this is allowed from the Apple In-App-Payment policies, but Paypal has a pretty ok API. You could use that to transfer money.
I recommend you that reading:
http://developer.apple.com/library/ios/#documentation/NetworkingInternet/Conceptual/StoreKitGuide/Introduction/Introduction.html Maybe that is of help too