Have you taken it to a good gunsmith?
I am just running an idea by here, before replacing the barrel I would have the crown of the muzzle checked, it may just need a simple recrowning of the muzzle,
It has all the symptoms of a damaged muzzle crown.