dpkg: error: info database format (2) is bogus or too new; try getting a newer dpkg

Version: 16.04 HWE
Kernel: 4.15.0-91-generic

wdeberry@PLC-b362c669-da248f5c:~$ sudo apt install --reinstall nvidia-340
Reading package lists... Done
Building dependency tree
Reading state information... Done
0 upgraded, 0 newly installed, 1 reinstalled, 0 to remove and 0 not upgraded.
Need to get 0 B/51.6 MB of archives.
After this operation, 0 B of additional disk space will be used.
debconf: delaying package configuration, since apt-utils is not installed
dpkg: error: info database format (2) is bogus or too new; try getting a newer dpkg
E: Sub-process /usr/bin/dpkg returned an error code (2)

Disclaimer: We run our own mirrors which is why the URLs/Domains are not the stock Ubuntu ones.
wdeberry@PLC-b362c669-da248f5c:~$ apt-cache policy dpkg
dpkg:
  Installed: 1.18.4ubuntu1.6
  Candidate: 1.18.4ubuntu1.6
  Version table:
 *** 1.18.4ubuntu1.6 500
        500 https://plc.internal.getwellnetwork.com/apt-plc4 test/xenial-updates/main amd64 Packages
        100 /var/lib/dpkg/status
     1.18.4ubuntu1 500
        500 https://plc.internal.getwellnetwork.com/apt-plc4 test/xenial/main amd64 Packages

wdeberry@PLC-b362c669-da248f5c:~$ cat /var/lib/dpkg/info/format
1

Worked with the #ubuntu channel and they had me do the following to no avail:
* sudo rm -rf /var/lib/apt/lists
* sudo apt autoclean
* sudo apt update && sudo apt-full upgrade

The only thing that lets me move on is to sudo rm /var/lib/dpkg/info/format. I have done this on one machine and the issue has now come back a day later.