A manual cleanup is really the only way if you want to keep the detail.

Alternatively, you can make the sole a seperate object and use the shrinkwrap modifier to fit to shape. Add a cube and make sure it is a little larger than the sole and has enough subdivisions to get the detail then add the modifer to the cube. The cube mesh will shrink to fit.

Hope that helps.