The huge plumes above Mars' southern hemisphere were first spotted by amateur astronomers on two separate occasions in March and April 2012.
But despite almost three years of analysis, scientists are still stumped as to what could be causing them. Their best guess is that the plumes were either a very bright aurora or an extremely large cloud.
"Importantly, both explanations defy our current understanding of Mars' upper atmosphere," the authors write in Nature, where their results have been published.
The fact that there are clouds on Mars isn't unusual - the Martian atmosphere has plenty of clouds in it - but these plumes are far higher than anything seen before, stretching up to 250 km in altitude. Similar clouds have not reached beyond 100 km, and any dust storms have only been spotted up to 60 km high.
The clouds also stretched for up to 1,000 km, which makes them the biggest ever seen.
"At about 250 km, the division between the atmosphere and outer space is very thin, so the reported plumes are extremely unexpected," said lead author Agustin Sanchez-Lavega of the Universidad del País Vasco in Spain in a press release.
The mist-like clouds appeared in less than 10 hours, but were visible for around 10 days. Unfortunately, none of the spacecraft orbiting Mars were in a position to spot the plumes, but a search of old Hubble images revealed a similar giant cloud on 17 May 1997, which you can see below.
"One idea we've discussed is that the features are caused by a reflective cloud of water-ice, carbon dioxide-ice or dust particles," said Agustin in the release. "But this would require exceptional deviations from standard atmospheric circulation models to explain cloud formations at such high altitudes."
This would also mean that the temperature in the Martian atmosphere would need to have dropped around 100 degrees Celsius, the authors report.
Their other hypothesis is that the plumes were auroras - similar to the southern lights on Earth. "Auroras have been previously observed at these locations, linked to a known region on the surface where there is a large anomaly in the crustal magnetic field," said Antonio Garcia Munoz, a research fellow at the European Space Agency and co-author of the paper, in the release.
But if this is the case, the auroras would have been ridiculously bright, and solar activity at the time can't explain such a light show. "It would be 1,000 times stronger than the strongest aurora, and it is difficult to come to terms that Mars has such an intense aurora," Garcia Munoz told Rebecca Morelle for BBC News.
"It raises more questions than answers," he added.
It's now hoped that the European Space Agency's ExoMars Trace Gas Orbiter, which is set to launch in 2016, will shed some much-needed light on the issue. The researchers also hope that their paper might inspire astronomers and atmospheric experts to come up with other hypotheses.
In the meantime, let's not jump to any conclusions.