Makes sense now, that partuuid only applies to the mender_root variable and not to the mender_grub_storage_device.
I can not think of an easy way to get around this, because GRUB is not able to scan/probe for a partuuid.
But I know of one user who has solved a similar problem using the GRUB search command, which supports looking up filesystem image by label or fs-uuid. But this would require changes to the grub.cfg file + making sure that the partitions are labeled accordingly on each update.