Some thoughts I had:
* You are spot on in concluding that this is a tool that would be used a few of times in a year. A lifetime payment is the solution, with an appropriate price bump of course.
* Regarding the users that signed up for free: You should have allowed them to keep using the service for free. They are your implicit marketing team. They got in early, they deserve gratis access for that.
* Regarding the recurring scheme of cancellations: Do contact the users, ask them why they are leaving. This will help you either validate my first thought above, or iterate on the service to become what they expect to get out of it.