When was the very first verifiable time the name "Maxine" was used or
mentioned in any type of text or book or historical record or
whatever?

Leslie Dunkling and William Gosling, The New American Dictionary of
First Names, p.289, dates the popularity of the name 'Maxine' to the
late 1930s, prompted by the actress Maxine Elliott.  It is widely
believed to be a French name, but that is incorrect: It is English and
American.  In origin, it is simply a feminization of 'Max'.