I was actually contacted a few years ago by a company who I, unbeknownst to me, essentially owned shares of and had the certificates.
They had been my dad's when he died, filed in a file of stocks that he believed were worthless but he liked how the stock certificates looked and had always talked about framing them and hanging them on the wall. He may have in turn inherited them from his father who died in '71 - these were old certificates.
Rather than being worthless, they were for a Canadian energy company that, through a chain of acquisitions, became a part of Encana. The company name looked pretty sketchy and they were probably acquired by someone by the time he was dealing with it, so I don't blame him for thinking they were worthless.
As best I can recall, I mailed Encana the certificates I had, they mailed me Encana certificates, and I endorsed and mailed the Encana ones to Fidelity who had no problem dealing with it. Conceptually, it's pretty much like depositing the stocks at at your broker.
Cost basis was pretty hard to even guess at, but the stockholder relations folks at Encana were able to give me the stock price for the dominant predecessor company at the end of 1992. Since my dad died 12/30/92, I said "close enough" and used that. The IRS hasn't complained yet, and it wasn't that much money - I think I ultimately got $1800 when I sold the Encana stock.