Earlier quoted context omitted.
Many local governments publish shapefiles (geojson) that have address information. You could parse out addresses and have a fairly simple free option. Since this data is based on property taxes, these data sets aren't going to be missing parcels (or the tax collector would be missing potential revenue).
That still leaves out a lot: unincorporated lands, First Nation reserves, small settlement where all the mail goes to a post office instead of individual buildings, etc. Also, one of the main benefits from Canada Post API is that it gives you the canonical address Canada Post uses to deliver packages. I don't think this always overlaps with addresses municipalities use to assess taxes. For example, I can imagine for…
A poor man's approach could be to query the publicly available data sets, and use that data when there's match. Then, only pay for queries that fall into the edge cases.