Sadly, it only works for apps that were not minimized when invisible. A better workaround requires a shortcut that "un-minimizes" all windows and then minimizes them... I tried WIN+M for minimizing and WIN+SHIFT+M for un-minimizing, but the latter only un-minimizes the ones that were minimized with the former, so it's also not an ideal workaround...
EDIT: By doing virtual desktop switching and all of these hotkey combinations in quick succession, something weird happened. One of the "stuck" icons was not 100% invisible, but it was shifted down so that only the tip of the icon was showing at the bottom of the taskbar...
What if the icons aren't missing (it's not a problem of corrupted thumb/icon cache as that workaround doesn't work), instead there's some animation glitch that drops them to a (very far off-screen) Y position?