What would happen if you send them an email stating your wish to cancel and then asked your CC company to deny any charges from them? I'd think that would be a legal and valid way to cancel any service.
They send to collections. Personally I find a certified letter to their registered agent is the best method when I think a company might be shady and I don't wanna wait on the phone.
For the states I've been curious about in the United States, each state's Secretary of State usually has a search form for corporations, LLCs, and limited partnerships. examples: California (http://kepler.sos.ca.gov/) and Washington (http://www.sos.wa.gov/corps/).
It depends where you are, but many places have something broadly similar. Here in England, for example, any limited company must have a registered address and mail to that address must be read. The registered address must be shown in various places by the company, and can also be checked by anyone through Companies House, which is the government authority that deals with such things. These are all legal requirements here, and the authorities will not look kindly on a company that doesn't follow the rules, with potentially serious implications for its directors.
It's the person on record who should be contacted for legal matters, correspondence, etc.
Essentially, if these things ever get to court if you contacted someone other than the agent they can claim they weren't notified, didn't know, etc, if they are shady, but a registered letter to the registered agent is like the gold standard of having contacted them.
I removed subscriptions from a few services that way and none gave me any problems. Even reactivated some of the accounts later on when I decided to go back. Most of those used paypal, so I think they got cancel notifications straight away.
I can't remember the names of most of the companies though. One was definitely Match, because they expect you to call them to cancel (or did at the time)
I'd think that would be a legal and valid way to cancel any service.
Please be careful. That is not necessarily the case, and depending on your local laws you may be left owing money, going to collections, and/or having your credit damaged for non-payment.