Suppose I have a message in my email client with full headers, but the message isn't available in Gmail anymore. In a copyright infringement dispute or something similar, can that message be used as some kind of proof? Can headers prove that the message and its content are legitimate?
Most people overlook the statement “everything on the internet is forever”, but in the modern age, this is a reality. During discovery it isn’t uncommon for opposing counsel to request large amounts of e-mail documentation, including documentation that has been deleted, but is still stored on the server of the email provider or in the meta-data from the computer being analyzed (email recovery is usually done by a third party, professionals at data recovery).
Under Rule 26 of the Federal rules of civil proceeding, electronic documentation is categorized under the same rules that govern paper documentation during discovery.
Can it be used?
This is a tricky question to answer because the answer is, yes, it CAN be used, but WILL it be used depends on if there was a successful motion filed with the court to suppress this evidence.
More exactly, it can be offered in evidence. As the answer by @StephanS says, it may well be possible to establish that the email was sent by various recovery methods, which are frequently used in legal cases. But even if it were impossible to establish through third-party sources that the email was authentic, it could be offered based on testimony by the party offering it that it was actually sent. Such testimony might or might not be believed, just like all testimony. But it can be offered. Admissibility would be subject to rulings by the Judge, of course.