So, by now the problem seems to have resolved itself. I installed several machines today, following the same installation procedure, and now they all succeed.
Nevertheless, this morning I spoke to a Microsoft Support engineer and he told me that it was basically a synchronization issue and that I should just hide the update and forget about it.
From what I'm being told, resolving the problem so that the update isn't even offered as a candidate is very time consuming and will only result in the update not being installed, and the same can be achieved simply by not installing it (what a surprise).
He also noted that the code 9C48 in this context basically means the update is already installed/not required, which would match our observations.
Another interesting idea came from a business partner of ours.
He proposed that the issue only happened because when I was offered to install updates, after the initial installation of Windows, I chose to install all available updates. Even those that aren't checked by default:
He proposed that this leads to a problematic state which results in the error in question. Supposedly only installing mandatory and pre-selected updates will avoid the issue.
Sadly, because the problem can't be reproduced right now, I am unable to confirm this, but it sounds plausible.