I've used Acrobits SoftPhone (link goes to their site, iTunes link below) for some time, thought admittedly very sparsely and only for the simplest of use cases, so, much of this is taken from their site.
Use the OS' Address Book: Yep, it maintains it's own "quick list" (favorites) however.
and global Recent Calls list: Nope, maintains it's own (pretty sure this one is impossible anyways, "private APIs" and all that).
Load as fast as Phone.app: I call this subjective, because Phone.app is always running, which gives it an inherit speedup compared to anything else. Acro's SoftPhone does support the VoIP backgrounding, and even push, so you can "Swipe To Answer", but it still takes at least a couple seconds to do. (At least that's how it feels, comparatively speaking.)
International Number Support: I think this is not so much a client feature as much as it is a feature of your server you SIP register to. This one is unknown to me as I've never attempted to call an international (outside the US) number.
Allow Recording: Yes. Upon tapping the record button, a voice announcement is played, and then conversation is recorded and able to be replayed from the app.
Skype: Nope
Google Voice: Yep, but to what extent, I am unsure. Per their website:
GoogleVoice users: Though we have integrated GoogleVoice, Acrobits Softphone's main use is as a SIP client. You can setup Acrobits Softphone to initiate GoogleVoice calls through other types of numbers, but to get the full functionality of Acrobits Softphone, you need to have GoogleVoice linked to a SIP Account.
Rest: If it's SIP, it should work.
Bonus: It supports ZRTP. Zimmerman's encrypted RTP protocol for SIP calls. Free for incoming calls, in-app purchase for initiating calls using it.
iTunes Link: Acrobits Softphone.
Best Answer
I prefer Telephone App over most the other VOIP clients I have come accross.