Is there an equivalent of the Better Business Bureau (BBB) in Canada? Contacting the BBB and filing a claim is definitely a way to get some momentum, lots of businesses in the USA at least depend on having a good, clean BBB rating.
Did the company in question ever say that they were an SEO firm in their sales pitch or just an online marketing agency?
Personally, I would contact the medical board, see a lawyer about what the doctor's rights are, and file a UDRP domain dispute to get ahold of that domain name.
There is a big difference between a company that's a web advertising company and an SEO company or SEO firm. Lots of agencies do SEO and web advertising, but to put a blanket statement out there that this was an SEO firm (meaning Search Engine Optimization firm interested in getting organic/natural traffic to a site) is wrong.
This shady company is a web advertising company, who put up a false/misleading website on a misleading domain name. It doesn't sound like their intention was to do SEO. They make money by charging the doctor or clinic for the website and they "maybe" get some local listing, perhaps do PPC. But typically a company like this doesn't have the expertise or knowledge (or care) to do real SEO (which requires real content and link earning).
Don't get me wrong, what the company did here was false, misleading, and punishable. But to put a blanket statement out there and assume that this was an "SEO firm" or "SEO startup" is just flat out wrong.
This original post should say that the doctor was contacted by an "agency" and not an "SEO startup".