Melissa was last seen at a holiday party in the Woodside Apartment Clubhouse, at approximately 10:00 p.m. on December 3, 1989 in Lorton, Virginia. Her family resided in the apartment complex. Melissa and her mother were about to leave the party but Melissa went to get some more potato chips before they left, and was never seen again. There were approximately eighty guests present at the party at the time.

Caleb Daniel Hughes emerged as a suspect in Melissa's case almost immediately. Hughes was employed as a groundskeeper at Woodside Apartments at the time of Melissa's disappearance; he had worked there for only about two weeks. He was a guest at Melissa's family's party the evening of her disappearance, had been sitting near her when she was last seen, and left at approximately the same time the child was discovered missing. He had a criminal record prior to Melissa's disappearance, but not for violent or sexual offenses.

Investigators looked for Hughes right after Melissa's disappearance was discovered, but did not find him until 1:00 a.m. the next day. He had already put his party clothes in the washing machine. The Federal Bureau Of Investigation (FBI) examined took blood, hair and fiber evidence from Hughes's maroon Honda and tested it in a forensic laboratory. The laboratory found that Melissa could be a source for the hair and the bloodstains, which were found on some tissues in the car, but so could 40% of the general population. Further testing ruled out Melissa as a source for the stains. However, rabbit hairs found in the car matched Melissa's rabbit-fur jacket and there were many blue fibers that matched her sweater and some red fibers consistent with her skirt.

Hughes was convicted of abducting Melissa with the intent to defile in 1991, and sentenced to 50 years in prison. He has always maintained his innocence in Melissa's case. He is an inmate at Bland Correctional Center and his expected release date is October 2025.

Two other men were convicted of attempting to extort ransom money from Melissa's mother shortly after her daughter's disappearance. The individuals were not connected to her actual abduction. Melissa has never been located. Foul play is suspected in her case due to the circumstances involved.