Gwent Police are checking all missing persons records after a pair of feet in training shoes were washed up in the Severn Estuary.
Two fishermen found the body parts, in size eight Diadora trainers, near the Second Severn Crossing at the weekend.
Detectives have since ruled out a connection with a woman, aged 38, whose body was washed up on riverbanks in February.
Instead, they are contacting families of missing persons, including Manic Street Preachers guitarist Richey Edwards, to trace the owner of the remains.
The rock star, who would now be aged 34, vanished seven years ago before his car was found abandoned at a Severn service station two weeks later.
One of the found feet - caked in mud along with socks and believed to be that of a man - was discovered at Sudbrook near Chepstow on Sunday evening.
Gwent Police later found the second after a search of the area, but a search on Monday morning by the Severn Area Rescue Association did not find additional remains.
Detectives said the blue-and-white trainers were washed up on a recent high tide.
Woman ruled out
A Home Office pathologist has now ruled out a link with the body of a woman whose body was washed ashore at Peterstone Wentlooge between Cardiff and Newport during February.
That has prompted Gwent Police to check all missing persons files in the force area and in neighbouring Avon and Somerset, South Wales and Gloucestershire.
Manic Street Preachers member Richey Edwards has not been seen since he checked out of the Embassy Hotel in London on 1 February, 1995.
He dropped off some possessions at his Cardiff Bay flat before driving away.
There were several apparent sightings of Edwards in Newport before, on 14 February, his Vauxhall Cavalier was found at the Severn service station in Aust near the first Severn Bridge.
That is around two miles upstream from the scene of the feet discovery.
He could have been declared legally dead by his parents this February, but the family maintains Richey is alive and merely missing.
A Gwent Police spokesperson said Monday: "We are checking on all missing persons including Richey Edwards.
"The human remains had been in the water for some time and may have been dislodged by a recent high tide."
"It is very gruesome," the spokesperson added.
"The fisherman thought it was just an old training shoe but, when he looked closer, he could see there was a sock inside with bones sticking out.
"The fact that the other foot was nearby suggests that the person had entered the water not too far away."
He said the body may have lay at a nearby sandbank, with the rest of the remains already dislodged and carried downstream due to the extent of decomposition.
The estuary has experienced several high tides in recent weeks and has the second largest tidal range in the world.
[Originally published: bbc.co.uk/news/wales, 26 March 2002]