There's 30 days worth of data at http://www.otcmarkets.com/marketActivity/symbol-changes - but I'm really looking for the past 10 years, or 5 years if only that is possible. Any dice?
The closest I've come, and this is not really cutting it, is looking up a stock via Yahoo! Finance and seeing "TICKER is no longer valid. It has changed to NEWTICKER".
But that's not helpful; for example in the case of Skye industries, it used to trade as SKYY. But now SKYY tracks some sort of cloud computing ETF.
Happy to pay for the data.