I would contact a tax professional in your jurisdiction for assistance. They may contact the relevant tax authorities to negotiate an mutually acceptable solution to the lost records. This should serve as an important reminder to never rely on third party providers to store financial information that is needed for tax purposes. Instead one should store electronic financial records on computers under one's control, running Free Libre Open Source Software (such as GNU/Linux), with multiple redundant backups and in a format that is readable by Free Libre Open Source Software.
By the way I expect a fair amount of grief among former MTGox clients over lost / inaccessible records as the various tax deadlines around the world approach April 30th (Canada), April 15th (United States) etc.
I think I can build the needed data from other sources. Having shifted from reading IRS pubs to getting data organized relating to BTC purchases, it's tedious but doable.
I don't particularly trust tax software. I suspect they have a yearly renewal and I recall an unpleasant surprise from a Physicians Desk Reference on CD one year which cropped up in January the following year. I'd like to see something in Debian or Ubuntu archives that would do a data plug and play on the US IRS 1040. So many suggested possible alternative ways to file there have to be some ways better than others.
Noting a suggestion to return a letter of explanation along with the tax return while reading IRS pubs, it seems like the best way to go. First time moving beyond the 1040A. I think if I explain what I'm doing clearly the worst that will happen if incorrect is directions as to the correct docs to use.
But yes, your suggestion to consult a tax professional is a good one. I've heard many times over the years that a tax professional knows well some limits for deductions beyond which trigger a problem, the hint being that some things will be padded. Bitcoin is fairly new but yet it's been around a few years. The upper limits on transaction fees might be one way a pro could cook up a return that might be better than one can do oneself. But what the hell.