The fugitives are some of the last members of the Red Army Faction, which sowed terror in Germany in the 1970s and 80s with kidnappings, nearly 300 bombings and 34 killings.
Now, after being at large for decades, the three far-left terrorists have been linked to at least six supermarket heists, prosecutors said on Tuesday.
On top of that, the trio has also been pegged in a series of attacks against money transporters, using grenade launchers.
And authorities believe that the list of crimes carried out by the three suspects - Ernst-Volker Staub, 61, Burhard Garweg, 47 and Daniela Klette, 57 - is far longer than earlier thought, dating back five years to 2011.
"The investigations... show that the suspects in the money transporter attacks... could also have carried out the attacks at supermarket cash offices," said the prosecutors in the northern state of Lower Saxony.
"The culprits are believed to be short of money, hence further attacks cannot be ruled out," they warned.
Between €46,000 and €100,000 were stolen in each hold-up, except for the most recent on May 7th, when the robbers escaped with a guard's firearm but no cash.
Authorities said they had drawn the link between the six robberies across Lower Saxony and Schleswig-Holstein states after finding a similar modus operandi in all of the cases.
The fugitives are believed to be holed up in either Germany or neighbouring countries, as in one case, a telephone call made to a car-seller was traced to the Netherlands.
Experts have previously said that the group is probably not trying to start up another terrorism wave, but rather fund their daily needs, especially as they grow old.
'Calm, polite, sober'
In each heist, one suspect would head to a garage to purchase a cheap used car for under €3,000, but would sit in the passenger seat during the test drive.
The car was always paided for in cash, but picked up at a later time outside business hours.
"In the attacks, they use pistols and sometimes electric stun guns to threaten supermarket staff or cash carriers either as they enter or leave the cash offices," said prosecutors.
"The behaviour of the culprits is calm, polite and sober," the prosecutors said, adding that the suspects sometimes also stress that they "are only after the money".
After leaving the crime scene, the suspects then hide the getaway vehicle, usually in forest areas, before fleeing with another car.
"They try to remove any trail by setting the getaway vehicles on fire, but did not always manage to do so," said prosecutors.
The three are among a wider group of fugitives still on the run for membership of the anti-capitalist RAF, also known as the Baader-Meinhof gang, which emerged out of the radicalized fringe of the 1960s student protest movement.
The group, which had links to Middle Eastern militant organisations, declared itself disbanded in 1998.
Staub, Garweg and Klette, alleged members of the RAF's so-called "third generation", have long been wanted as chief suspects in a 1993 explosives attack against a prison under construction in Hesse.
In the attack, five RAF members climbed the prison walls, tied up and abducted the guards in a van, then returned to set off explosions that caused about €600,000 worth of property damage, said prosecutors.
Klette is also a suspect in two previous RAF operations, prosecutors said - a 1990 failed car bomb attack against a Deutsche Bank building near Frankfurt, and a 1991 attack in which a gunman fired at least 250 shots at the former US embassy in Bonn, without causing any casualties.