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.
His clients are the ones accepting payments though, so they need Canadian merchant accounts. Beanstream accepts Canadian merchants. We just started the sign up process with them last week, from Victoria BC.