The new find, published in the journal Historical Biology, confirms what scientists have long suspected -- that Osedax were likely responsible for erasing parts of the fossil record by destroying bones before they could become fossils.

Worms from the Osedax genus do not have a mouth or gut but consume the bone by growing root-like tissues, which dissolve the bone as they grow.

Lead scientist Nicholas Higgs discovered tell-tale traces of Osedax in the Mediterranean last year using micro-CT (Computed Tomography) scanning technology as part of his PhD at the University of Leeds and the Natural History Museum.

He says: "After several promising leads came to a dead end, the scans from the final sample looked different and I knew that I was on to something."

Osedax were first discovered alive in 2002 in Monterey Bay, California, where they were living on the bones of a decaying gray whale.

Since then, scientists have been curious about how the worms might have affected fossil records, but understanding when Osedax evolved and where they lived in the past has until now remained a problem because actual remains of soft-bodied Osedax do not preserve as fossils.

The only way to tell where and when Osedax have been at work is by distinctive bulb-shaped cavities that they leave behind in a bone -- and it is these borings that have finally been recognised by Higgs.

His research shows how widespread Osedax were millions of years ago.

The only other known evidence of Osedax from the past is in whale bones from the Pacific coast of Washington State in the US -- about as far away as it is possible to get from the Mediterranean in terms of ocean connectedness.

When Mediterranean dried up almost six million years ago most deep sea animals were killed. About half a million years later the sea re-flooded from the Atlantic.

Higgs says: "So finding out that Osedax were feeding on this whale bone three million years ago tell us that their ancestors must have also been living in the Atlantic as well, because the Mediterranean was re-colonised 5.5 million years ago from the Atlantic."

It is now almost certain that the Mediterranean is currently host to undiscovered, living Osedax species, Higgs says.

"There are 20 different species in Monterey, California alone, so it's almost certain there are many more out there. If Osedax were living the Mediterranean three million years ago there's no reason why they aren't living there now."

Last year, Higgs travelled to California to examine living Osedax and their borings to help understand and identify the full range of known species.