Well, there could be a possible solution to your first problem: offer both a high priced one-time removal attempt, or a recurring subscription with a minimum contractual obligation (6 months for example).