The renewed zeal for cracking down on illegal cigarette sales did not stop with smuggling and interstate border shopping. In the 1970s, government officials in Michigan and other states turned their attention to the sales of tax-free cigarettes on Indian reservations. Smokers looking to evade state cigarette sales and excise taxes had long been patronizing the reservations since Indian tribes are sovereign nations.
In 1978 the NTTA's Committee on Tax Evasion's "Report of Indian Cigarette Tax Litigation" warned of substantial revenue losses and stated that others besides state officials should be concerned about the continued sale of tax-free cigarettes in smokeshops:
Cigarette manufacturers and distributors should be concerned because these tax losses must be made up by increases in other taxes, some of which will inevitably fall upon them. ... Even Indian retailers should be concerned, because the consequences of such drastic losses of state tax revenues will inevitably result in more demands for an end to the historical tax immunities which Indians have enjoyed.
Officials in various states, as part of their overall efforts to reclaim lost cigarette tax revenue, began demanding that merchants on Native American lands start remitting tax on their cigarette sales to non-Indians. Hence, tax-induced smuggling was now straining relations between state government and both cigarette manufacturers and Indian reservations.
Tribal leaders were not initially compliant, and litigation ensued in some states, including California, Washington and New York. During the protracted legal battles, the ambiguity of the law and the potential for a huge profit led to the opening of numerous "smokeshops" on tribal lands, often accompanied by aggressive marketing. State policymakers' hands seemed to be tied as courts debated the law, and various states tried to negotiate with individual tribes.
Michigan entered into negotiations with tribal leaders, and the decade closed with a victory for the state in limiting tax-free cigarette sales. The Michigan Treasury Department negotiated an agreement with the Bay Mills Indian Tribal Council, which took effect in 1979, limiting the number of tax-free cigarettes the tribe could purchase annually. The number was calculated by multiplying Michigan's per-capita cigarette consumption by the number of tribe members living on the reservation, and then subtracting the 25 percent of cigarettes that were estimated to be purchased by Indians off the reservation. The agreement also allowed the state to conduct an annual audit, and the tribe agreed to pay the excess tax if it purchased more than the allotted number of cigarettes in one year.
Courts have generally ruled that cigarettes sold on tribal lands to Native Americans are exempt from state excise taxes unless authorized by federal law. However, sales to non-Indians are generally held to be taxable. In 1980 the U.S. Supreme Court reached a decision in the case of Confederated Tribes of the Colville Indian Reservation v. State of Washington. Originally a federal district court had ruled in favor of the tribes, explaining that they had adopted a tax of their own already, which pre-empted the state tax; adding state taxes to the tribal tax would violate the tribes' right of self-government.
The U.S. Supreme Court, however, held that states could require the tribes to collect cigarette taxes on sales to non-Indians. In 1985, the U.S. Supreme Court decided California State Board of Equalization v. Chemehuevi Indian Tribe, holding that California could require Indian reservations to collect cigarette taxes on sales to non-Indians.
In response to a questionnaire that the National Association of Tax Administrators sent to the states in 1985, Michigan indicated that its negotiations with tribal leaders had "ended the Indian smokeshop problem." A 2006 report from the state Treasury Department recounted the success of the negotiations:
[T]he Department of Treasury has committed significant time and resources toward establishing relationships with the various Michigan tribes and developing specific protocols to help guard against the inappropriate distribution of untaxed cigarettes. These efforts, with the assistance of many of the tribes, have resulted in a significantly enhanced enforcement regime.
A specific example of such effort was the Department-led negotiations with the federally recognized tribes located in Michigan, where the States and the Tribes got together in an effort to obtain broad tax agreements that address a variety of taxes, including tobacco. ... This two-year process resulted in agreements with eight of the 12 tribes. ... [T]hese agreements cooperatively ensure the collection of Michigan tobacco taxes by providing specific protocols for sales within "Indian Country" as well as enforcement provisions allowing the state to audit and inspect within these sovereign lands.
With regards to those tribes which do not have an agreement with the State ... the Department of Treasury continues to monitor and enforce State tax laws, to the extent allowed by federal law. These efforts have resulted in a number of cigarette seizures and a considerable amount of litigation. To date, the State has prevailed in all such litigation with the most recent decision coming from the U.S. District Court specifically upholding the Department's established protocols.
The Treasury report also included data on the number of packs of cigarettes sold in the state between 1993 and 2003 that were tax-exempt. This data listed not only sales on Indian reservations but also sales on military bases, which will be discussed below. According to the report, tax-exempt sales comprised 0.90 percent of total sales in 1993, jumped to a high of 1.71 percent in 1995, gradually fell to 0.60 percent in 2001 and finally rose slightly to 0.82 percent in 2003.
Military base sales appear to have originally been a larger problem. In 1995, over 13 million untaxed packs were sold on Michigan military bases, while only 327,621 were sold on Indian reservations. By 1999 smokeshop sales had eclipsed military sales, and in 2003 approximately 2.3 million untaxed packs were sold on military bases, compared to approximately 3.4 million on reservations. According to Scott Darragh of the Office of Revenue and Tax Analysis with the Michigan Department of Treasury, the state no longer keeps official data on sales at Indian reservations and military bases.
 Committee on Tax Evasion, "Review of Indian Cigarette Tax Litigation," in Proceedings from the 52nd Annual Meetings of the National Tobacco Tax Association (Chicago: Federation of Tax Administrators, 1978), 51.
 Robert C. Pitcher, "Report on an NATA Survey on State Cigarette Inspection Programs and Indian Smokeshops," National Association of Tax Administrators, in Proceedings from the 59th Annual Meetings of the National Tobacco Tax Association (Chicago: Federation of Tax Administrators, 1985), 13.
 Michigan Tobacco Enforcement, (2006), 3.
 Ibid, 3-4.
 Michigan Department of Treasury, Michigan's Cigarette and Tobacco Taxes 2004, October 2005, 14.
 James Hohman, Mackinac Center for Public Policy, telephone interview with Scott Darragh, Michigan Department of Treasury's Office of Revenue and Tax Analysis, November 24, 2008.