I'm tempted to suggest that this practice actually far predates the creation of keys. I believe Renaissance and Medieval church pieces were often categorized by which of the 8 Church Modes they were written in. This would tell a church musician a lot about the mood, or ethos, of the piece, and aid the singers in knowing what scale to use. Speculating... it may also have suggested other pieces in similar (or contrasting) moods that could be arranged with it. In short, a piece's identity had much to do with it's mode -- much like how a book's genre determines much of its linguistic form and content.
Later, when music shifted from modes to keys, there was some initial confusion (at least by some) about the difference between the two systems, but at any rate, it made sense to keep referring to pieces by their tonality. Once again, a piece's key was closely tied to it's character. Especially in the days before equal temperament, when different keys were considered to have different characters.
Another consideration is that composers often didn't bother naming or numbering their own works -- for example, the Brandenburg Concertos were actually merely titled "Six Concertos for Several Instruments". So any system that can distinguish between two pieces is fair game. This includes listing the form (e.g. "Concerto"), the key (e.g. "in F Major"), and the instrumentation (e.g. "for Trumpet, Recorder, Oboe, Violin, Strings, and Continuo"). Together with the composer's name (e.g. "by J. S. Bach"), this is often enough to identify the specific piece, or at least narrow down the possibilities significantly. Even when pieces are explicitly numbered, these other factors are more meaningful than an arbitrary number.
You'll notice that when pieces do have a specific name, the key designation is used considerably less: Vivaldi's "Spring" vs. "Violin Concerto in E Major"; Beethoven's "Choral Symphony" vs. "Symphony No. 9 in D Major"; Sousa's "Stars and Stripes Forever" vs. "March in ... whatever key Stars and Stripes is in..."