This is a very interesting question, especially for those who like a bit of historical mystery.

During the Restoration, Louis XVIII ordered for an investigation to be conducted in order not only to find his brother's and Marie Antoinette's bodies, but also his nephew's ( Louis XVII ) and his sister Madame Elisabeth's.

It is not correct to say that Louis XVI and Marie Antoinette were buried in mass graves, they were buried in graves much more profound than the usual ( to prevent people from desecrated but more importantly from making a cult to the former king ) but they were not mixed with other corpses. This was not the case of Madame Elisabeth for example, whose body was dumped with other people's corpses.

I will use the information gathered by Paul and Pierrette Girault de Coursac, who have certainly revolutionized what we know of Louis XVI and Marie Antoinette in the 20th century ( though not without polemics, I will mention it if something is subject to controversy ). Their work on the royal bodies remain one of the best however.

---

When Louis XVIII gained power, he wanted his family's bodies to be found. This was certainly for both political and sentimental reasons. Despite their differences in terms of politics, Louis XVI and Louis XVIII had been quite close ( much more than with their brother Artois, future Charles X ). Very important, he also wanted to find Louis XVI's son, the " Prince of the Temple " . Indeed, many people believed he was alive ( of course, what happened to him is still a mystery ) and this was dangerous for Louis XVIII's legitimacy. The more traditionalist royalists would say that a XVIII was second in line until Louis XVII had children of his own, the other who were " enemies " of the new monarch could use this as a weapon against him. In any case, after some 30 years of constant wars and civil turmoils, a question of legitimacy between the Bourbons was the last thing France needed and Louis XVIII knew that. Secondly, finding Louis XVI and Marie Antoinette's bodies could finally give them funerals according to the religion and the tradition of the French monarchy.

Louis XVIII charged his chancellor ( Charles-Henri Dambray ) to find the bodies. As it was only two decades after the facts, the first task was to find witnesses of the burial and after some time, he found several direct witnesses. Amongst them were a judge, the abbot ( a constitutional abbot, authorized to give Louis XVI's last rites ), a worker who dug and closed the King's grave and the owner of the cemetery's land ( his father - I think it was, or close relative - lived right next to the cemetery and watched the whole scene, he was a strong royalist and as soon as the cemetery was on sale bought and preserved it ). These witnesses helped to visualize how the burial went. Thankfully, the owner of the land protect the graves very well by creating some sort of garden around where the bodies were, as well as planting a weeping willow to mark the places of Louis XVI and Marie Antoinette's graves.

So they started digging at the emplacements, without knowing who they would find first. According to the orders given two decades earlier, the bodies should be around 12 feet deep. They found Marie Antoinette first by hitting lime at around 8 feet deep.They found woods from the coffin, bones, the entire skull and some sort of garter that the Queen made herself, it allowed to identify the body as her's. On the other hand, the body of Louis XVI is another matter. The Girault de Coursac are partisans of a conspiracy started by Louis XVIII stating that the former monarch's body was either never found or never truly identified as his and that the one they presented by a fake ( well, someone else's ). Anyway, a body was indeed found, without a doubt at the exact emplacement where Louis XVI was buried. The only thing that differed from Marie Antoinette is that they did not found anything that proved it was his.

When they dug to find Louis XVI, they found a body that had not been preserved as well as Marie Antoinette's. Like for the Queen, they found wood, bones ( some turned to dust immediately ) and " parts of the body ' that mixed with the lime. The lime simply recovered parts of the body and simply added to the bones Louis XVIII refused that anything be attempted " to extract it ". They placed the remains in a coffin ( parts of the old coffin, bones, dust and a part shape of Louis XVI body ).

The authorities dug all around to be sure they had found the King's remains and did not found other remains around. The other corpses had been dumped elsewhere in the cemetery, living the royal couple close to each other and alone. There is no doubts that their bodies had been found. There is just no proof ( other than the location and the fact he was near Marie Antoinette ) it was Louis XVI that was found. The Girault de Coursac, as I said, thought of a conspiracy ( more an attempt by Louis XVIII to hide the fact he did not found his brother's body ) and spread the idea. However, what they use to verify this is very thin. They said that if it was Louis XVI, the ring of his coronation should have been found with the remains. This is a very fine theory as nothing says he worse the ring for his execution, no witness says it and it would have been very hard to take it from his body ( the finger would have had to be cut and unless one of them did it, the soldiers present would have prevented it ). To that the de Coursac answered that he had to wear it for his death as it was a deeply religious element ( the ring of his consecration as king ) but we know he gave to Marie Antoinette his wedding ring ( just as religious ) on the eve of the execution. So nothing says he had it, plus if ring there is it could be stuck in the untouched lime and in this case nobody knows it ). The de Coursac used pretty much all the possible ideas to argue that it is not Louis XVI's body that was reburied during the Restoration but a fake. Louis XVIII simply ordered the searches to stop, simply because he believed to have found the body or did not hope to find " another one with a real proof ".

To conclude, there is no doubt Marie Antoinette's body was found. For Louis XVI, there is 99,9% chance that he was indeed found and so far nobody really came with a standing theory. Both were found in their graves, thanks to the witnesses, Louis XVIII's police and investigators and the fact that they had not been dumped with dozens other corpses like so many other people.

Sources : Enquête sur le procès du Roi Louis XVI by Paul and Pierrette Girault de Coursac Provence et Artois : les deux frères de Louis XVI by Paul and Pierrette Girault de Coursac

Hope this helps, feel free to ask anything if you did not understood something I wrote ( English is not my native language).

The story goes that a Royalist, Pierre-Louis Olivier Desclozeaux, who lived adjacent to the Madeleine cemetery noted carefully where the two were buried and bought the area when the land became publicly available in 1802 and he marked the what he believed to be the burial site with a hedge and several trees. During the Napoleonic period, the Madeleine Cemetery became something of a local Royalist shrine and tourist destination, a sort benign opposition that the Napoleonic regime begrudgingly tolerated. Desclozeaux sold the land back to the state during the Bourbon restoration and an excavation is undertaken to find the corpse of the king and queen based upon Desclozeaux's memory and those of other witnesses. The corpses are allegedly identified by scraps of clothing for the Marie-Antoinette, the remnants of a coffin, and the fact that their location matched where several witnesses claimed they were interred.

As counter-intuitive as it might sound, the lack of evidence played into the Bourbon legitimation strategies which emphasized both providence and a revivified spiritual Catholicism. There were multiple miracle stories and rumors that surrounded the bodies and Louis XVIII was not anxious to disprove them. The exhumation and reinterring in St Denis had highly religious overtones of resurrection of the Bourbon dynasty by lacing the remains in the crypts of the French monarchs rather than a common grave.

There were of course skeptics as to whether or not the corpses really were the king and queen. One popular urban legend that grew out of Paul Barras's memoirs and bragging was that he had Robespierre thrown into the same grave as Louis XVI at the last minute and that the body interred in St Denis is really the head of the Committee of Public Safety. However, Barras seems to be the sole originator of this tale and there is no corroborating evidence to support his tale.

Source

Baecque, Antoine de, and Charlotte Mandell. Glory and terror: seven deaths under the French Revolution. New York: Routledge, 2001.