When I was a kid in small-town Ontario, buying tax-free cigarettes was a lot like buying marijuana - you went to the guy who was known to sell them, who was usually hanging around the high school, and he hooked you up.
In my day the cigarettes were name brands, sold to low-tax American states and then smuggled back into Canada through Indian reservations - you couldn't tell you were smoking smuggled cigarettes by looking at the butts. Now Indian reservations manufacture their own untaxed cigarettes - which is completely legal, when bought and smoked on the reservation. However, they're also illegally sold off the reservation.
In Ontario at least, it's against the law to buy these cigarettes off the reservation. The penalty is a fine. Enforcement, for the individual buyers, is pretty much non-existent.