How can I code a class so that it will have permission to add and delete contact objects, even when the invoking user doesn't, and not use "without sharing" (SalesForce security review won't allow it)?

The class is an entry point in a managed package, and must pass security review, so "without sharing" is not allowed, neither is omitting the sharing clause. The class sends emails using templates, which requires each addressee to have a Contact object. Therefore, it must create temporary Contact objects and then delete them after the email is sent.