You might already tried some of these, or maybe it won't be helpful, but either way, here is some suggestions to start with.
1) It's probably not this simple to fix, but then again it's a quick and cheap trial and error test to check and be sure. Try clean old update data. "sudo apt-get clean" in the debian-9 terminal. I'm not sure how to clean old data in dom0 or the sys-firewall, or wherever Qubes 4 new update mechanism keeps its downloaded packages before sending them to the "offline" updating template in question. But perhaps this is something to look further into, atm I don't have too much time to do so. If it keeps hanging on the same %, then perhaps this is a possible suspect, and maybe a cleanup fixes it.
2) Does restarting all of Qubes, and immediately update debian-9 after full startup, make any difference? I.e. I've experienced issues on longer running Qubes 4 my self, but mostly my issues are triggered by suspend/hibernate or if HDMI plugged TV-screen goes to sleep mode on its own (even if laptop screen is not sleeping). It triggers various of weird system issues, I'm suspecting it's driver-module/kernel related, but I'm not really all that sure. A full system restart however, makes everything work fully again. Perhaps you experience something similar, yet different at the same time. Either way, quick way to find out whether a full restart works or not.
3) How about "sudo journalctl --boot" in dom0 and AppVM terminal alike, same time, after you did both a system restart and then following also encounter the update bug. Doing it after a system restart cleans the log and make it easier to read. Aka, easier to scroll down to the last lines that matter, and doing it right after you encounter the issue, makes it a possibility to spot some errors in the log, around the end of it. (I'm sure there are smarter ways to navigate these long scrolling, but none that I'm aware of). Doing this both in the AppVM and dom0, same time, and look for something that looks out of the ordinary. Also executing both commands same time, before looking into the logs details, makes it a bit easier, so you don't have to mess with time-log comparisons.
I know these are relative simple approaches, but I can't think of anything deeper atm. If above suggestions are to no prevail, then maybe someone more knowledgeable will drop by with better suggestions.
True, I also use current-testing on my Qubes RC-2, fully updated, which has debian-9, and do not experience these update issues either. If only using regular updates, perhaps the issue is indeed fixed in the current-testing releases.
Might want to backup first though, just in case current-testing gives rise to other more serious problems.
It really does sound like the new backup method for templates yeah, so it's probably revolving around python code and packages related to the admin mechanic, type of updates?
aha, this should narrow it down to possible suspects indeed.
Just to be sure, there might still be a possibility that the restart fixed another issue, of an origin we didn't speculate about. Was it a single case issue the restart fixed? Or do you encounter repeatedly issues after hibernation which are fixed with restarts? Just to verify, so we don't jump to conclusions too fast.
I'm guessing your issue is pretty much similar to my own, except we experience somewhat different symptoms, originating from the same cause - hibernate/suspend. You can see my github issue rapport here from a few weeks back (I haven't had the time to keep the rapport updated due to emerging deadlines hunting me down, but I plan to return to it eventually. Also it was different back then, the issue I rapported back then has changed somewhat (slightly) between that date and today. I plan to update there soon as well);
https://github.com/QubesOS/qubes-issues/issues/3359
Feel free to add your own experiences of the issue if you think it has similar root causes. The symptoms might be different, but the cause/trigger appears to the similar.
Possibly it's the admin mechanism that breaks down? I experience issues in the domU windows, like the Qubes coloured panels, or Qubes widgets, general graphical freezes, or entire forced restarts during suspend because it doesn't suspend while in my bag but stays awake when it's supposed to be suspending, etc. Perhaps, your issue is similar, but you get networking issues instead, i.e. when updating.
So all this might be somehow related to the admin mechanism, I'm speculating now though, but it seems like a good place to start given the clues so far seems indirectly to point towards it.
You can throw a link there back to this thread on github, if you find it useful to do so, if you decide to make a post on the github thread. If you don't plan to post on github, do you mind if I link to this thread instead for extra references? Once I get around to it of course. I think it's a good idea to show more people have this issue (assuming it indeed has a shared trigger/cause), perhaps it can provide extra clues of the overall bug.
The problem right now though, is to narrow it down more precisely, so the exact issue can be found.
Also, something that changed in recent updates (I'm sitting on current-testing updates), is that it now appears to be enough to only restart all network based VM's (non network based VM's are fine and don't need restart). Basically, sys-net and sys-firewall are messed up. This makes it easier, as it no longer requires a full system restart. Is this the same for you too?