O Is for Outlaw handles the concept of distorted memories primarily through the personal story of Millhone. The mystery in which she is engaged pertains to her personal history and requires a reappraisal of the behavior of her first ex-husband, whom she discovers she judged wrongly. What she reveals in her investigation of his shooting reverses what she had thought about him: now she finds he was "guilty of infidelity, innocent of manslaughter." Such a reappraisal touches upon the novel's concern with the dislocation between appearances and reality. Millhone had judged her ex-husband, Mickey Magruder, upon circumstantial evidence when he was accused of manslaughter. The fact that he had been a cop who "chafed at the limitations set by policy and, on a broader level, at legal restrictions he felt interfered with his effectiveness", and that he had asked Millhone to provide him with an alibi for some crucial hours for which he could not account, made her leave him. Millhone has lived with the version of the past that she created, and her misjudgement, for fifteen years.

Echoing this plot-centric revision of the past, the effects of the Vietnam War on its participants reverberates throughout the novel, mostly in the form of physical damage. The character in whose death Magruder was implicated was a veteran, with a metal plate in his head as a result of the war. This contributes, ultimately, to his death in the year following its end. Living with a physical reminder of the war is also central to another character's life—Eric Hightower, who lost both legs. He presently runs a successful business manufacturing equipment for people with disabilities. Interestingly, it is Hightower's disability, which can be seen, that is integrated into society successfully while that which cannot be seen, the victim Benny Quintero's, is excised, a reversal that rehearses the surface/ reality dichotomy running through detective fiction as a genre. This dichotomy is made much more explicit between Hightower and Mark Bethel, the Vietnam veteran whose sins during the War and subsequent to it are exposed during the course of the novel. As an open and visible totem of the past, Hightower is embraced by society, but Bethel and his secrets are not. Bethel does not suffer from a physical handicap as a result of the War and his corruption is represented as an individual matter, not resulting from any social factors. His character is the epitome of the split between surface and reality, for he presents himself as the upright figure running for public office, concerned, in fact, with obtaining a fair deal for Vietnam veterans, while his actions attempt to conceal his own dishonorable behavior. In its representation of the veterans, the novel does not question the involvement of the United States in Vietnam—the subject of contemporary debate—but upholds the conservative version of events of the past.

The version of the past that Millhone had created for herself on a personal level, however, is overturned by her discoveries. As she gradually realizes the error of her judgement, she becomes concerned that she set right that misjudgement by finding the person who shot Magruder, reinforcing the sense of justice and personal integrity which courses through the central protagonist: "if I'd been an unwitting accomplice to his [Magruder's] downfall, I needed to own up to it and get square with him." This sense of attaining justice on a personal level is intertwined with the overarching concerns of the detective novel genre, and finds its literalization in the final scene where the perpetrator is brought to an end in a rather Biblical "eye...