Does anyone know the earliest instances of the pas de deux? Also, Did it always consist of entrée, adagio, two variations and a coda (or something close to that)? I am having trouble finding information on this in the books I have access to.

S. N. Hammond is a prominent scholar and historian who has done work related to your subject.
Here's what the New York Public Library gives in one response to a query about Pas de Duex and Hammond:

Hammond, Sandra Noll.
Windows into romantic ballet : content and structure of four early nineteenth century pas de deux.
Society of Dance History Scholars (U.S.). Conference (20th : 1997 : Barnard College). Proceedings. p. 137-144. ill.
Examination of four pas de deux by Michel St. Léon, Pierre Gardel, Jean-Pierre Aumer, and Albert (François Decombe) created and performed between 1820 and 1825.
Paper presented at the 20th annual conference of the Society of Dance History Scholars held at Barnard College, New York City, June 1997.
Includes bibliographical references (p. 143)