JK Rowling has actually addressed this very subject, at Carnegie Hall in 2007:
Question: When Harry was stabbed by a basilisk in the Chamber of Secrets,
since he was a Horcrux shouldn’t it have been destroyed then?
JK Rowling: 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.