I did some searching in archival and current newspaper databases, for both literal and figurative uses of the phrase. It appeared frequently in the 19th and 20th centuries, and it's not unusual to find it in recent headlines and articles as well.
The Original Meaning Of The Term
In its literal and original sense, as you would expect, the term was used in the 19th century to describe the activities of Native Americans:
"The acting commissioner of Indian affairs to-day received a telegram from Agent Roorke of the Klamath (Oregon) agency, dated July 6, in which he says: 'No Indians are off the reservation without authority. All my Indians are loyal and peaceable, and doing well." (Baltimore Sun, July 11, 1878)
"Secretary Hoke Smith...has requested of the Secretary of War the aid of the United States troops to arrest a band of Navajo Indians living off the reservation near American Valley, New Mexico, who have been killing cattle, etc." (Washington Post, May 23, 1894)
"Apaches off the reservation...killing deer and gathering wild fruits." (New York Times, Sept. 7, 1897)
Many of the news articles that used the term in a literal sense in the past were also expressing undisguised contempt and hatred, or, at best, condescension for Native Americans — "shiftless, untameable...a rampant and intractable enemy to civilization" (New York Times, Oct. 27, 1886).
