We can speak of clearing a computer memory meaning re-initialising storage, and of deleting or erasing information in a computer, which may amount to the same (depending on the system). Clear has more of a connotation of the physical memory storage, whereas erase and delete have more of a connotation of the actual data.
If we say that a person has a clear memory of a specific event, we mean that he remembers every detail of the event. This is in contrast to a vague memory in which only certain aspects of an event can be recalled, and perhaps the person is unsure about them even.
If the man in the example has a clear memory of the woman then he remembers everything about her, what she was wearing when they met, the time of day, the music playing, every detail of their conversation etc.
To say that the man's memories of the woman were cleared may not be a good way of saying he had forgotten all about her, because the association of having a clear memory conveys the opposite.
Even if it is clear in the context that you are using a computer analogy, erase or delete work best because it is the "data" about her that has become irretrievable, rather than the brain cells and neurons that have been reset.