I have encountered this error also. Was setting up a new server and after applying the service pack, the windows update would generate the exact same error codd. However from another box, an update would be successful. I suspect that the issue may be something that Microsoft has implemented as a protection scheme. (this is a guess at this point) The server I was working with had been installed with a Key Code which duplicated another system. They had valid licenses, but had used the same key code to install the OS.
To get around the error, I generated the usual list of updates, then I wrote down the Q numbers of each update. Then I did a search for those q updates and installed the needed files manually.
This is not an answer,but it may give you something to work with.