The Collaborative International Dictionary of English v.0.48:

Vestige \Ves"tige\, n. [F., from L. vestigium footprint, trace,
   sign; the last part (-stigium) is probably akin to E. sty, v.
   i. Cf. Investigate.]
   1. The mark of the foot left on the earth; a track or
      footstep; a trace; a sign; hence, a faint mark or visible
      sign left by something which is lost, or has perished, or
      is no longer present; remains; as, the vestiges of ancient
      magnificence in Palmyra; vestiges of former population.
      [1913 Webster]

            What vestiges of liberty or property have they left?
                                                  --Burke.
      [1913 Webster]

            Ridicule has followed the vestiges of Truth, but
            never usurped her place.              --Landor.
      [1913 Webster]

   2. (Biol.) A small, degenerate, or imperfectly developed part
      or organ which has been more fully developed in some past
      generation.
      [Webster 1913 Suppl.]

   Syn: Trace; mark; sign; token.

   Usage: Vestige, Trace. These words agree in marking some
          indications of the past, but differ to some extent in
          their use and application. Vestige is used chiefly in
          a figurative sense, for the remains of something long
          passed away; as, the vestiges of ancient times;
          vestiges of the creation. A trace is literally
          something drawn out in a line, and may be used in this
          its primary sense, or figuratively, to denote a sign
          or evidence left by something that has passed by, or
          ceased to exist. Vestige usually supposes some
          definite object of the past to be left behind; while a
          trace may be a mere indication that something has been
          present or is present; as, traces of former
          population; a trace of poison in a given substance.
          [1913 Webster]

WordNet (r) 3.0 (2006):

vestige
    n 1: an indication that something has been present; "there
         wasn't a trace of evidence for the claim"; "a tincture of
         condescension" [syn: trace, vestige, tincture,
         shadow]

Moby Thesaurus II by Grady Ward, 1.0:

177 Moby Thesaurus words for "vestige":
   account, afterglow, afterimage, ancient manuscript, annals,
   antique, antiquity, archaism, artifact, balance, boss, bump, butt,
   butt end, candle ends, catalog, catchword, cave painting, chaff,
   chronicle, clue, colophon, concavity, convexity, correspondence,
   cue, cue word, dactylogram, dactylograph, dash, debris, dent,
   detritus, dint, documentation, embossment, end, eolith, evidence,
   excrescence, fag end, filings, fingerprint, footmark, footprint,
   footstep, fossil, fossil footprint, fragment, glimmer, hint,
   history, holdover, hot lead, husks, ichnite, ichnolite, impress,
   impression, imprint, indent, indentation, indention, infusion,
   inkling, intimation, inventory, key, key word, lead, leavings,
   leftovers, letters, list, lump, mark, memento, memorial, mezzolith,
   microlith, neolith, odds and ends, offscourings, orts, pad,
   paleolith, parings, path, paw print, pawmark, petrification,
   petrified forest, petrified wood, petroglyph, pimple, pipe roll,
   plateaulith, print, pug, pugmark, rag, rags, record, recording,
   refuse, register, registry, relic, relics, reliquiae, remainder,
   remains, remnant, residue, residuum, rest, roach, roll, rolls,
   roster, rota, rubbish, ruin, ruins, rump, sauce, sawdust, scent,
   scourings, scrap, scraps, scroll, seal, seasoning, shade, shadow,
   shavings, sigil, sign, signet, smack, soupcon, spice, spoor,
   sprinkling, stamp, step, straw, stubble, stud, stump, suggestion,
   survival, suspicion, sweepings, table, tag, taint, taste, telltale,
   tempering, thought, thumbmark, thumbprint, tinct, tincture, tinge,
   tint, tip-off, token, touch, trace, track, tract, trail, waste,
   whiff