As per Łukasz's request, I have performed verification testing across a wide range of affected and unaffected systems, with the grub2-2.02~beta2-36ubuntu3.23 package in -proposed.

All tests were performed on GCP.

Test case one:

Summary: efi enabled image with 3072gb disk.
Disk: 3072gb
Bios/efi: efi
Image: daily-ubuntu-1604-xenial-v20190731, ubuntu-os-cloud-devel
Affected: Yes

Behaviour with grub2-2.02~beta2-36ubuntu3.22 from -updates:
Fails to reboot - as expected because of this bug.
Log: https://paste.ubuntu.com/p/KKH7r3vdrC/

Behaviour with grub2-2.02~beta2-36ubuntu3.23 from -proposed:
If you follow the instructions in the test section, the instance reboots successfully. Note, grub-install must be explicitly called. If you do not manually run grub-install, rebooting will fail. 
Log: https://paste.ubuntu.com/p/7KxmDCjFSG/
Log (apt upgrade, no manual grub-install): https://paste.ubuntu.com/p/j3VK5PV7GR/

Test case two:

Summary: efi enabled image with 10gb disk.
Disk: 10gb
Bios/efi: efi
Image: daily-ubuntu-1604-xenial-v20190731, ubuntu-os-cloud-devel
Affected: No

Behaviour with grub2-2.02~beta2-36ubuntu3.22 from -updates:
Reboots successfully.

Behaviour with grub2-2.02~beta2-36ubuntu3.23 from -proposed:
Reboots successfully. 

Logs: https://paste.ubuntu.com/p/c65jjYjj6S/
Note, grub-install was not invoked manually, and represents a typical user apt upgrade with no interaction.

Test case three:

Summary: bios enabled image with 10gb disk.
Disk: 10gb
Bios/efi: bios
Image: ubuntu-1604-xenial-v20191024
Affected: No

Behaviour with grub2-2.02~beta2-36ubuntu3.22 from -updates:
Reboots successfully.

Behaviour with grub2-2.02~beta2-36ubuntu3.23 from -proposed:
Reboots successfully. 

Logs: https://paste.ubuntu.com/p/N3QFX63WCS/
Note, grub-install was not invoked manually, and represents a typical user apt upgrade with no interaction.

Test case four:

Summary: bios enabled image with 3072gb disk.
Disk: 3072gb
Bios/efi: bios
Image: ubuntu-1604-xenial-v20191024
Affected: No

Behaviour with grub2-2.02~beta2-36ubuntu3.22 from -updates:
Reboots successfully.

Behaviour with grub2-2.02~beta2-36ubuntu3.23 from -proposed:
Reboots successfully. 

Logs: https://paste.ubuntu.com/p/KZw4kcD6pS/
Note, grub-install was not invoked manually, and represents a typical user apt upgrade with no interaction.
Log (apt upgrade, WITH manual grub-install): https://paste.ubuntu.com/p/RFBR5BbbtH/

Conclusion:

grub2-2.02~beta2-36ubuntu3.23 from -proposed fixes this bug. It does not introduce any regressions for non-affected use cases.

The only thing to note, is that for efi based images with disk > 2tb, if the user does not manually run grub-install after installing the package in -proposed then rebooting will fail. This is no better than the current situation of failing to reboot regardless, and because of this, there is unlikely to be any users out there who are running an image with disk > 2tb and have never rebooted ever, so it is unlikely this will be a problem.

This will however, fix all images and new instances using the fixed version of grub moving forward.

Taking this into consideration, I am happy to mark this as verified.

Pat, feel free to also test. I will also see if the customer is interested in testing as well.