How does one document Bitcoin investments for tax and other legal issues?
What legal documents to keep?  That's really a question for your accountant and/or attorney. One could reasonably expect to need about the same level of documentation as would be required for an investment in stamps or coins. 

Most likely the exchanges comply with AML (Anti-Money-Laundering) statutes in their own jurisdictions, but the onus is probably on the individual to obtain documentation of all transactions.