One solution would be to regularly send them an email (maybe once every three months) with the request that to send you their updated information (via email).
I wouldn't want the app to send this sort of communication in my name.
Would you use a new app that makes the "search contact(s) → call/write/message" faster and more beautiful?
The standard ios app is quick and pretty enough for me.
If a friend also uses your app, can you mark their contact details as being guaranteed-up-to-date? → That is the idea that I want to build the app around.
If a particular friend doesn't use your app, can you remember when I entered their details and keep track of how stale they are? → Good point. One solution would be to regularly send them an email (maybe once every three months) with the request that to send you their updated information (via email).
If I text them and the text doesn't get through, can you highlight their number as possibly not working any more? → That wouldn't be necessary after they use the same network as well. Otherwise: Cool idea, I will add it to the list.