But Awlaki had gone.
Jyllands-Posten is in possession of an e-mail purportedly from Awlaki to Storm, dated January 17, 2010.
"Do you remember the guy you lived with? It is now confirmed that he has been killed," the cleric wrote.
The newspaper says it also has taped telephone conversations between Storm and PET agents.
The USB gambit
According to Storm, it was more than a year before another attempt was made to track down Awlaki.
Storm recounts a two-day meeting in April 2011 with PET agents at a hotel in Helsingor, overlooking the Baltic Sea. It was decided it would be too dangerous for Storm to return to try to meet Awlaki, but he would travel to the Yemeni capital and then send a USB stick to Awlaki via a messenger.
Before leaving, he sent a message to the editors of "Inspire," the online magazine published by al Qaeda in the Arabian Peninsula (AQAP), using the codename Awlaki had given him - "Polar Bear."
In June 2011, he made a five-day visit to Sanaa, followed by a longer one in July.
Storm says he was given three rendezvous on different days - one of them at a KFC in Sanaa.
It was a typical precaution on the part of Awlaki and al Qaeda.
At the third location, the messenger passed him a list from Awlaki of what he needed.
The USB stick, with encrypted messages, became their means of communication.
At one point, Awlaki asked what was being reported in the West about alleged plans by AQAP to use the poison ricin.
At about the same time, the New York Times reported: "American counterterrorism officials are increasingly concerned that the most dangerous regional arm of Al Qaeda is trying to produce the lethal poison ricin, to be packed around small explosives for attacks against the United States."
One typed message from Awlaki included a personal request, perhaps illustrating the close relationship the two had forged.
"My wife needs some stuff from Sanaa so can your wife buy it for her?" he asked.
Storm says he was recalled to Europe in August 2011, and met with both CIA agents and PET officials in Malaga, Spain.
He claims he was told by "the American" that there was plenty of reward money should Awlaki be killed.
In September 2011, Storm says he received a message from an intermediary, who took the USB stick back to Yemen.
"I heard later....that the messenger had come to the shopping center, had the USB connector and was driven away in a Toyota Land Cruiser," Storm told Jyllens-Posten.
Three weeks later, Anwar al Awlaki was dead.
U.S. officials maintained that a separate intelligence stream had led them to Awlaki's location. Storm didn't believe them.
Falling out with the Americans
"I am convinced that the CIA seized the messenger..... but the Americans apparently won't recognize that it was an agent of PET and the small country, Denmark, which led to the detection of Anwar," Storm told Jyllands-Posten.