Maybe you could install a local mail client like Thunderbird and connect it to your Gmail via POP3? POP will download the mails and delete them from the server. Then you’ll just have to figure out how to export the mails from Thunderbird/your client of choice.
EDIT: This article contains relevant information.
EDIT 2: Alternativly you could just use IMAP instead of POP to download everything and then delete the mails from the server manually.
What a nice thing to say to one of your senior employees. HR people really are something else. They could’ve easily lost him that day because of some random bullshit.