Containing a soul fragment does not make a physical object indestructible in and of itself (as we can see from the fact that Harry's body can be injured). A soul fragment does seem to inherently possess a few special powers, like being able to think on its own to some degree and being able to possess people in certain circumstances, but there is no indication as far as I recall that durability is one of the inherent powers that a soul fragment confers to its container.
Therefore, it's likely that the reason why a Horcrux is mostly indestructible is merely because it is enchanted to be so by its creator. See the answers to What makes a Horcrux object (almost) indestructible? for more arguments supporting this.
The creator of a Horcrux chooses to cast many additional spells on the Horcrux, in addition to the Horcrux-creating spell, to give it additional safeguards and protections. From a JKR interview1:
I think, by definition, a Horcrux has to be made intentionally. [... Harry] didn't have curses upon him that the other Horcruxes had.
Voldemort is a wizard; he cannot use all kinds of magic (for example, house elf magic, goblin magic, or phoenix magic might be able to do some things that wizard magic can't do). So rather than "beyond magical repair", it would be more accurate to think of the criterion for destroying a Horcrux as "beyond the ability of (present-day) wizardry to repair." (That is, Hermione is implicitly using a wizard-centric view of "magical repair".)
In the world of Harry Potter, wizardry can do many things (as we see from things like the "Permanent Sticking Charm"), but there are limits to its power. The damage done by basilisk venom apparently cannot be repaired effectively with any known spell, so a Horcrux creator cannot enchant the Horcrux to be immune to Basilisk venom. It's irrelevant that phoenix tears can heal Basilisk venom. Wizards evidently cannot just conjure up phoenix tears, and the same restriction must also apply to Horcruxes.
- "PotterCast Interviews J.K. Rowling, part one." PotterCast #130, 17 December 2007.