Go with Beanstream as the payment gateway, and either Chargify or Recurly for the recurring payments. I've personally had no problem with this combination on many projects, and all of my clients are canadian companies.
We're going with Beanstream + Chargify. You might want to take a look at this: http://expletiveinserted.com/2011/10/02/stripes-new-online-p...