Thanks for your patch!
It also seems to fix some issues with menus unexpectedly closing in e.g. Kate or Thunderbird.

Can this potentially throw off the order of items or cause items to be removed that got inserted previously (ID clash?)? Quick testing suggests it's all working fine, however. :)

I can see the menu sometimes flickering showing that it briefly has more actions than it used to be. Reproducible in Krita's "Window" menu when using title bar menu button and interacting with the menu. After a while it also crashes.
Perhaps we should could do this only if the menu would become empty when removing the actions?

Can this potentially throw off the order of items or cause items to be removed that got inserted previously (ID clash?)?

As far as I can see, it should not be the case: those two operations should be totally interchangeable.
Both "insert/update" and "remove" actions are based on rootItem.children (which contains new layout of menu). Menu items that are inside it got updated, those who are not - got removed.

I can see the menu sometimes flickering showing that it briefly has more actions than it used to be. Reproducible in Krita's "Window" menu when using title bar menu button and interacting with the menu. After a while it also crashes.

Thanks for the testing!
By "crashing" you mean literally application crashing or just menu gets closed? I was able to reproduce it (the second option) on LyX with title bar menu button; apparently, its behavior is somewhat different from the plasma applet. Will look into it.

Perhaps we should could do this only if the menu would become empty when removing the actions?

We can. But my wild guess is that there will be probably also some flickering, but the other way around (i.e. briefly show it has fewer actions).
Actually, I don't see how we can avoid it.

UPD: we can probably wrap this code with menu->setUpdatesEnabled(false / true)?

UPD2: but libdbusmenu-qt inside plasma-workspace has no connection with appmenu from titlebar, right? (I guess the latter is done with KWin)

Ping?

From what I can tell this patch trades one bug (menu closing unexpectedly) for another one (menus erratically resizing/repositioning themselves).
I think we should be updating the actions in lockstep rather than adding all the things and then removing the old ones or vice-versa.

In D15637#335295, @broulik wrote:

From what I can tell this patch trades one bug (menu closing unexpectedly) for another one (menus erratically resizing/repositioning themselves).

As for LyX it's not just menu closing unexpectedly, but it's just totally unusable: I cannot access menu using the applet at all. That was the main reason I started looking into it.

But as for glitches: what about proposed QWidget::setUpdatesEnabled calls? (funny, actually it doesn't work for LyX, because, apparently, when I open a menu, it decides to run GetLayout 5-10 times in a row, updating the menu each time and causing glitches. Weird, and I don't even know who is responsible for that)

I think we should be updating the actions in lockstep rather than adding all the things and then removing the old ones or vice-versa.

That does sound like a better way. But I don't really know how do updated items correspond with old ones, since they have different IDs.
In principle those can represent absolutely different actions - if application really decided to totally mess with the menu during runtime.