First, if you bought it in a specialized shop, a cellar, do contact the seller.
He might do some gesture, and it's an important information for him, if he has other in stock.
Make sure you use the right kind of corckscew : it shall have a pigtail shape instead of a straight one. This way it'll apply the torque and the pulling force more even on the wood, and shall have less accident. You may also try for a twin-prong cork puller, where blunt blade are pushed between cork and glass. They do even less damage to the cork.
Corks aren't suppose to live eternally : it's not unusual for bottle above twenty years to have some defect. 2004 is a bit early, but you might get the monday morning cork ...
In fact, some cellarmen changes corks every decades to make sure nothing dreadful happens.
You should at least taste it. If it has spoiled, you'll definitly know it in a few second ... and even before you take a sip, if you are careful to the scent.
- If it has gone bad ... well, make vinegar from it if you can't get help from the seller.
- If it has lost some flavour but you still enjoy the taste ... well enjoy your wine !
- If it tastes perfect ... why should you worry ? Any kind of rubbish that could have been dangerous was put inside the wine before it has been draught from the cask. The corks only let a little osmosis with oxygen over the years.
I do have a very few 1988 bordeaux with this problem. Nothing different with the "healthy corks"ones.