When Bonney's testimony proved worthless and his own trial began, he started to doubt whether Wallace would keep his end of the bargain. Bonney decided it was best to escape and return to his lawless life. Wallace considered this a negation of his agreement with Bonney.
Bonney was eventually captured in December 1880 and brought to trial. He petitioned Wallace hoping an agreement could still be made, but Wallace remained silent. Bonney was tried in late March 1881, convicted of murdering Sheriff Brady, and sentenced to hang. Bonney's death warrant was written in Wallace's own hand.
Yet, the death warrant proved worthless because a month later Bonney engineered his escape from jail, killing both his guards in the process. Bonney was eventually tracked down and shot by Sheriff Pat Garrett in July 1881.
As if the troubles of Lincoln County and the dealings with Billy the Kid were not enough to occupy his attention, Wallace also had to concern himself with the marauding Apaches lead by Victorio. Faced with life confined to the reservation and what he believed was certain extermination, Victorio was determined to resist. Leaving the reservation and using Mexico as a base of operations, Victorio and his party raided and massacred encroaching white settlements. Victorio was eventually killed by authorities in 1880. Wallace described Victorio as "an enemy not to be despised."
With all of the troubles New Mexico had to offer, it is not surprising that Wallace did not especially enjoy his time there. However, he did manage to legislate some educational reforms and witnessed the advent of the railroad to the territory. Perhaps, the greatest
accomplishment of Wallace and his wife was the salvaging of the territory's archives. It was also at Santa Fe's Palace of Governors that Wallace put the finishing touches on Ben-Hur.