The only way to destroy a Horcrux, as Hermione tells us, is to put it beyond magical repair. The cup, the locket, Nagini, the ring, and the diary are all destroyed by a sword or fang covered in basilisk venom. That's all of the Horcruxes except the diadem.
BUT basilisk venom has a cure: phoenix tears. That is magical repair. So where is the error here?
The only way to destroy a Horcrux, as Hermione tells us, is to put it beyond magical repair.
Not quite. Hermione tells us:
'It has to be something so destructive that the Horcrux can't repair itself. Basilisk venom only has one antidote, and it's incredibly rare -'
Harry Potter and the Deathly Hallows - p.90 - Bloomsbury - chapter 6, The Ghoul in Pyjamas
(Emphasis mine).
The point is that Basilisk venom is so destructive that there's only one way to repair the damage it causes. And that's with Phoenix tears. The Horcrux would not be able to repair itself if it were damaged by Basilisk venom and would quickly perish. Perhaps it could be saved by Phoenix tears, but it could not save itself. Hence, if you stab a Horcrux with something impregnated with Basilisk venom and you don't put any Phoenix tears on it very quickly, it is going to be destroyed.
Though phoenix tears are a cure for the damage done by basilisk venom, the basilisk venom will still do irreparable damage if not healed quickly by phoenix tears. Once phoenix tears are not administered in a short period of time, the damage will be done and the Horcrux object will be destroyed irreparably. Phoenix tears any time after that will be ineffective. When J.K. Rowling explains why being poisoned with basilisk venom didn’t kill the soul piece in Harry, she explains that Harry was mended before he was destroyed, and that phoenix tears have to be administered immediately or the basilisk venom makes the object irreparable, presumably even by phoenix tears.
Q: When Harry was stabbed by a basilisk in the Chamber of Secrets, since he was a Horcrux, shouldn't it have been destroyed then?
JKR: I have been asked that a lot. Harry was exceptionally fortunate in that he had Fawkes. So before he could be destroyed without repair, which is what is necessary to destroy a horcrux, he was mended. However, I made sure that Fawkes wasn't around the second time a Horcrux got stabbed by a basilisk fang, so the poison did its work and it was irreparable within a short period of time.... I established early in the book, Hermione says that you destroy a Horcrux by using something so powerful that there's no remedy. But she does say there is a remedy for basilisk poison but of course it has to be administered immediately and when they stab the cup later - boy I'm really blowing this for anyone who hasn't finished the book - there's Fawkes, is my answer. And thank you for giving me a chance to say that because people have argued that quite a lot.
- J.K. Rowling at Carnegie Hall (October 20, 2007)
Basilisk venom is a method for destroying Horcruxes because once it takes effect, it renders the object irreparable, and the only chance for possibly repairing it is immediately putting phoenix tears on it. That’s of course not something a Horcrux can do itself, despite their protective enchantments, so once it’s infected with basilisk venom, it’s unlikely it’d be ‘cured’ in time to save the soul piece. Once the soul piece is destroyed, even if the object comes into contact with phoenix tears, it’d be too late because the soul piece within it would already have been destroyed.
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.
