Your goal, while admirable, is impractical. There is no "Contacts application". Android has a standard Contacts content provider and related activities. That has been replaced by HTC (on Sense-enabled devices), by Motorola (on MOTOBLUR-enabled devices), and perhaps other OEMs as well. Combine that with the fact that there is no "hook/extend" mechanism for any of them, and I do not see how you can create what you are looking for.
The Android 2.0 revised Contacts API, particularly with multiple accounts, may give you more options. It may be you have to create some sort of account that represents your encrypted contacts, and you might have the hooks to do that. However, I have not had an opportunity to dig into the new API enough to say for certain whether this approach is or is not feasible. And, it still assumes that OEMs stop replacing the native Contacts stuff with their own, and that s far from certain.