As someone fromnEurope, I was in the same boat as you with a NY Times trial subscription. I didn't even tried to call them, since they not only require you to call them to cancel your subscription, but do it during US east coast office hours too.

In the end I just canceled the recurring payment contract at PayPal. A few weeks later I received a 'Sorry to see you go' email from them and that was it.

I'm not sure if credit cards also allow you to cancel recurring payment contracts, but sepa directdebit does (which is the payment method used if you used for example the Dutch iDeal payment method as initial payment.