Out of curiosity, why did you decide to make it a separate service from TweetingMachine? It seems like a natural extension of it. That being said, since you have both tools, I would consider approaching it in one of two ways.

First: give InboxCleaner away for free and use it to get registered users for TweetingMachine. I imagine if a user signs up and is happy with one tool you provide, they would be more inclined to pay $20/mo for another related tool. This seems like a great opportunity for some A/B testing as well.

Second: add InboxCleaner as a paid add-on for TweetingMachine. Your customers are paying $20/mo for the basic service, so you know they aren't afraid to pull out their wallets. Offer them a monthly inbox cleaning for an extra $1/mo. What's the difference between $20 and $21 when they're already paying you?

Also, your name might be inhibiting some initial click-throughs to your site. When I hear InboxCleaner, I immediately think email. Maybe this is because I'm not a heavy Twitter user, but it's something to think about.

One feature that might up the ante is email reminders to clean their inbox every 6 months or every year. It's something people will do probably rarely, which means they're likely to forget the name of the tool they used to do it or forget to do it altogether. You might offer a friendly reminder to do Spring cleaning on their inbox.

Anyway, I've really enjoyed reading your posts. They're some of the most practical real world case studies I've come across, as opposed to the "I'm making $2000 a week and only working 4 hours" drivel that's out there. Not that I wouldn't like to make $2000 in 4 hours a week.