Melon survives for >2000 years (AP, via Yahoo News)
Technically speaking, food doesn't spoil... other things in its environment spoil it. It's kind of counter-intuitive, since everyday experience says otherwise: if you leave a hunk of raw meat out on the counter it's gonna get really nasty really fast, through no directly visible means. But, as has been known for some time, it's actually all the bacteria & such on the dust particles floating around that actually are the problem.
Louis Pasteur demonstrated this first, with broth. (His experiment, and others, are described here.) Basically, he put the broth in a glass flask, boiled it to kill the existing (at the time still hypothetical) spoilage-causing 'germs', and then heated & bent the neck to make a trap for the ambient dust particles. He could then leave the broth for days and (in most cases) no fermentation or spoilage was observed.
Same thing with that melon, sounds like... it managed to get holed up in an environment hostile to microorganisms, and just kinda sat there until the archaeologists dug it up. It's kind of an ironic find, though, 'cause now that it's been exposed to open air it'll probably go bad within a couple of days.
Still... 2000-year shelf life? Hard to beat, that... ;-)