Once again, "complicated" seems to be the order of the day
Send a warning to the user that the application is no longer trusted with link back to the App Store for verification. Let them decide if they want to delete it.
See? That was easy wasn't it? I know, it doesn't make for a lucrative consultation bill or speaking engagement or book and even an article, but there you go.