The film opens as the shy, soft-spoken Joel Barish and the unrestrained free-spirit Clementine Kruczynski begin a relationship on a Long Island Rail Road train from Montauk, New York to Rockville Centre. They are almost immediately drawn to each other despite their different personalities, though both had felt the need to travel to Montauk that day. Although they do not realize it at the time, Joel and Clementine are, in fact, former lovers, now separated after having spent two years together. After a fight, Clementine had hired the New York City firm Lacuna, Inc. to erase all of her memories of their relationship. Upon discovering this from his friends Rob and Carrie, Joel was devastated and decided to undergo the procedure himself, a process that takes place while he sleeps.
Much of the film subsequently takes place in Joel's mind during this memory erasure procedure. As his memories are erased, he tries to evade the erasing effects of the procedure by hiding Clementine in remote parts of his unconscious. Joel finds himself revisiting them in reverse. Upon seeing happier times of love with Clementine from earlier in their relationship, he struggles to preserve at least some memory of her and his love for her. Despite his efforts to either hide the memories or wake up and stop the process, the memories are slowly erased. He comes to the last remaining memory of Clementine, the day he first had met her at a beach house in Montauk. As this memory disintegrates around them, she tells him, "Meet me in Montauk."
Separate, but related, story arcs, which revolve around the employees of Lacuna, are revealed during Joel's memory erasure. Patrick, one of the Lacuna technicians performing the erasure, uses Joel's memories and mannerisms to seduce Clementine. Mary, the Lacuna receptionist, is dating the other memory-erasing technician, Stan. During Joel's memory wipe, Mary discovers she had previously had an affair with Dr. Howard Mierzwiak, the married doctor who heads the company, and had agreed to have this erased from her memory when Dr. Mierzwiak's wife found out. On learning this, she asks Stan whether he knew about this, to which he claims that he didn't. Mary then quits her job and steals the company's records, and mails the two former clients their records from Lacuna.
The film returns to the present, after Joel and Clementine have met aboard the train. They both come upon their Lacuna records later that day, and react with shock and bewilderment, because they have no clear memory of having known each other, let alone having had a relationship and having had their memories erased. Joel beckons Clementine to start over; Clementine initially resists, pointing out it could go the same way. Joel accepts this, and they decide to attempt a relationship anyway, starting their life together anew.

Question: What was erased from Mary's mind? 
Answer: Memories of her affair with Dr. Mierzwiak. 
Alternative answer: Memories of an affair.