After the war he toyed with the idea of going back to Vietnam to search for the gear he abandoned, but success was so astronomically unlikely that he would quickly toss the idea aside.
Imagine his surprise this June when he picked up his phone and a stranger on the other end said, "Colonel, I have something that belongs to you. We found your lost helmet."
"I couldn't believe it, I was elated," said Randall, who is now 86 and lives with his wife on the edge of Black Forest. "It had been gone for 47 years. Can you even imagine?"
The stranger, a Vietnam vet named Gary "Paco" Gregg, told the old pilot a story of chance encounters, dead-end searches, Vietnamese flea markets, and an iconoclastic French sword maker in Cambodia who had been searching for the helmet's rightful owner for 22 years.
"I think I had tears in my eyes when I'm telling him this," said Gregg, who lives in Lincoln, Neb. "Finally, we had found the man!"
Soon the helmet was on its way from southeast Asia.
The tale of the helmet weaves together the worst and best aspects of humanity, beginning in war, where men who had never met went to great lengths to kill one another, and ending in peace, where men who had never met went to great lengths to help one another.
"It's pretty amazing," said Randall. "If it wasn't true, I wouldn't believe it."
'You had a job to do'
The day Randall was shot down in 1965, he was leading a flight of four F-105 fighter bombers to destroy a bridge in far northwestern Vietnam.
A major at the time, Randall had already flown 118 combat missions.
"All of them were dangerous," he said. But, he said, he did not dwell on the risk. "You had a job to do."
The son of a librarian and a railroad worker, Randall grew up during the Great Depression in the segregated schools of Roanoke, Va.
When World War II started, he yearned to become a pilot. A few men he knew had become Tuskegee Airmen - the first black military pilots who trained at Tuskegee Army Airfield in Alabama, starting in 1941. Randall signed up in 1945, as soon as he was old enough.
After basic training, he was sent to Tuskegee Army Airfield for pilot training.
The war ended and all pilot training was canceled. He was discharged in 1946 and applied to college, assuming he would never realize his flying dreams. Then in 1948 the War Department sent a letter asking him to become a pilot in the newly-formed, integrated, Air Force.
Randall graduated from fighter pilot school in 1950.
He was deployed to Korea in 1952, where he flew the P-51 Mustang on bombing missions to knock out bridges and rail lines.
Randall flew 75 combat missions over Korea.
"I got lucky. There were guns all over but I was never was shot down," he said on a recent afternoon in his home office. Even after the close calls of Korea, Randall never thought of leaving the Air Force.
"I just love flying," he said. "I never wanted to do anything else."
'Losses were appalling'
In Vietnam, Randall flew the F-105 Thunderchief single-seat fighter, nicknamed the "Thud," able to carry more explosives than the 10-man bombers of World War II.
He was part of Operation Rolling Thunder, an early attempt to cripple North Vietnam's fighting capability by destroying supplies and transport routes behind enemy lines.
Pilots streaked in from Thailand at high speed, dove over the targets and released about 6,000 pounds of bombs before thundering back over the border.
It was effective but dangerous. The Vietnamese had one of the best air defense systems in the world. The landscape bristled with anti-aircraft guns and missles.
When Randall arrived in August 1965, Thuds were being shot down at a rate of two per week.
"The losses were appalling," another F-105 pilot, Ed Rasimus, wrote in his 2003 book, "When Thunder Rolled." "For every five pilots that started the tour, three would not complete it."
In three years, 330 Thuds were lost, he wrote. By comparision, 74 aircraft have been shot down in Iraq and Afghanistan since 2003.
"You tried not to think about it," Randall said.
He had four kids at home.
The day he was shot down, Oct. 13, he had flown 43 missions in just over two months.
He was not particularly worried about his 44th. It was a simple hit and run, taking out a bridge 50 miles over the border near the town of Dien Bian Phu.
It was a clear day, perfect for flying. The Thuds flew high over the jungle of Laos, then, just over the border with North Vietnam, the mountains faded into a broad valley patched with farms and split by a twisting river.
That day, 15 other F-105s were hitting dams, roads and bridges all over Vietnam, according to press reports.
Ahead Randall saw the bridge.
The four bombers, flying in formation, prepared for their run.
They turned on the "pickle button" on their control sticks that would drop the bombs.
Randall pushed his Thud into a steep dive. The others followed.
Eight thousand feet above the bridge, he pushed the button, released the bombs, and pulled up.
Then he felt a sudden jolt. Anti-aircraft guns had hit the rear of his jet. Warning lights started going off.
"I knew right then I was in trouble," he remembered.
The gauge for the hydraulic system that powered the controls was dropping. The backup system was dropping too.
Randall watched the nose of the plane slowly come level with the horizon, then drop below.His control system was dead.
Nothing to do now but eject, he thought. He was still flying at about 600 mph.
Slight wind help his escape
The force of the ejection ripped off Randall's gloves and watch.
He opened his eyes, drifting thousands of feet above the valley. He could see a small village between his feet.
Of the 53 F-105 pilots who went down over Vietnam that year, 24 were rescued, 15 were captured, and 14 were killed.
Randall's first thought was "I'm not going home tonight."
He got lucky. A slight wind carried him across the valley to the edge of the jungle.
When he touched down, he pulled off his parachute and helmet and limped on a bleeding leg into the undergrowth. He crawled into the brushand watched with held breath as a group of men with rifles approached, picked up his helmet and other gear. They looked toward the jungle. Then they headed off toward the wreckage of the jet.
Randall worked his way uphill to a small clearing. There he radioed for help.
After waiting just over two hours, the whine of an American rescue party echoed over the valley.
Randall had never heard such a welcome sound, but the noise attracted the Vietnamese, who began shooting.
The helicopter hovered low over the clearing as it took fire. Randall raised up his hands and two men in the crew locked arms with him and pulled him aboard.
A few days later he was recuperating in the United States.
A long, winding road back to owner
What happened to the helmet is unknown.
Randall stayed in the Air Force for another 15 years and retired as a colonel in Colorado Springs in 1980.
In the years after the crash, he imagines, a villagertook his helmet and sold to someone else, who sold it to someone else, who sold it to someone else.
Somehow, the helmet traveled 1,000 miles south to Ho Chi Minh City, where in 1990 a Frenchman named Dominique Eluere, known worldwide for making fine samurai swords, spotted it at an Army surplus stall in the city's hardware market.
A student of military history, he paid a trifling amount he now doesn't recall.
In his home office, Eluere studied the helmet: It was hard, white plastic with a blue stripe down the middle. On the left side was a scuffed sticker of an eagle holding a sword under the words "562 Tac Fighter SQ" and on the right side, the word "Jim." In the middle, a small, embossed label read "Maj. Randall."
Seeing that he might have a chance of finding the owner, Eluere decided it was only right to return it.
"A helmet is something very personal. A kind of crest," Eluere said by email from Phnom Penh, Cambodia. "So if it would be mine, I'd love someone give it back to me."
He started searching in history books and then the Internet. When he met Americans, he would ask them for ideas of how to find the pilot. After several years of little progress, a journalist he met found records that showed the helmet was from the 562nd Tactical Fighter Squadron, which flew F-105s out of Thailand during the war, and that a "Maj. Randall" had been in the unit.
"But how to find him, and if he is still alive?" Eluere said. His quest was far from over.
In 2007, he became friends with Gregg, a retired stone worker from Nebraska who had fought in Khe Sahn, Vietnam in 1966 and 1967, and for years had been returning to Cambodia, working for a non-profit organization that provides education for the minority Montagnard people.
One day over beers, Gregg told Eluere he was also involved in tracking down information on troops who were missing in action. Eluere perked up.
Eluere showed Gregg the helmet.
"I would like to get this off my shelf. Let's find this man. You are an American, can you help me?" Gregg remembers him saying.
Gregg replied he would do the best he could.
"It proved darn near impossible," Gregg said in a phone interview.
The Air Force told him it had no record of a Maj. Randall shot down in Vietnam, he said. He eventually learned through historic records that there had been a pilot shot down named James Randall, but had no idea how to find a person with such a common name. Internet searches turned up nothing helpful.
In May, Gregg ran a notice in the Vietnam Veterans of America magazine asking if anyone had information.
A few weeks later, when Gregg was visiting his son for his grandson's graduation in Colorado Springs, he got an email from a former officer in Randall's squadron, saying Randall was still alive, and lived just a few miles away from where Gregg was.
Gregg called Randall immediately and they met the next day. Sitting around his son's kitchen table, they emailed Eluere, who sent back a photo of the white helmet.
"That's it!" said Randall, clapping his hands and laughing.
The helmet even had his oxygen mask attached.
A few days later, Eluere shipped the helmet to Gregg. Gregg plans to present the helmet to Randall at a gathering of the Tuskegee Airmen in St. Louis on Aug. 1.
"When you understand such long an uncertain search is over, you feel both joy and sorrow," Eluere said. "But we shall stick to joy. A good action is never lost. Only what is not given is lost. All the time the search last I had the idea to go and return the helmet myself against a hug and a cold beer. But when I received a message from Colonel Randall I understood it wouldn't be kind to let him wait any longer. So I shipped the helmet to Paco. I'm pretty sure he will drink the beer properly and with pleasure."
Randall smiles and shakes his head when he tells the story of the men who did so much to return his helmet.
"It's incredible," he said. "They could have kept it. They could have sold it. Instead they gave it back. I'd kind of like to know how the helmet got to that market in the first place, but I guess it doesn't really matter. It's here."
The walls of Randall's home office are covered with the accomplisments of his flying career: citations for the Bronze Star, Air Medal, Legion of Merit, models of the jets he flew and a copy of a painting of him from 1970 that hangs in the Pentagon. He plans to clear a spot for a custom glass case for his helmet.
"It's made it this far," he said. "I want to make sure it is taken care of."
Contact Dave Philipps