I ended up resolving this error by opting-out of Microsoft Update and then opting-in once again. I used ‘Actions > Windows Update > Opt-out’ followed by ‘Actions > Windows Update > Opt-in’. Now things work properly regardless of whether the server selection is set to ‘Windows Update’ or ‘Microsoft Update’. I have no idea why this fixed the problem or why the problem was happening in the first place, but I’m posting it here now in case anyone else runs into a similar issue.
EDIT/UPDATE 2021 – We have had a few reports of this issue over the past few years, and the above suggestion worked in each case.