Starnes was last seen in Stockbridge, Georgia at 8:45 a.m. on December 7, 2009. He dropped his grandmother off at her doctor's office off Highway 138, then went across the street to a Sunoco station, where he purchased a pack of cigarettes. He was supposed to pick up his grandmother after her appointment, but he never showed up and has never been heard from again.

Although Starnes is a heavy drinker, it's uncharacteristic of him to be out of touch with his loved ones. His family believes he was murdered. His grandmother, who raised him from childhood, died in August 2010 without knowing his fate. His disappearance remains unsolved.