WSUS can’t download anything, unclear why

I've got 2 WSUS servers:
An old W2K3, WSUS 3.0SP2 box and a brand new 2012 server with the WSUS role enabled.

The old machine works fine and pulls the updates from MS via the company proxy. (With BITS set to the default background mode.)
The new one has exactly the same configuration setup, including the proxy config en the same user-account for the proxy.
The new one will synchronize fine, even imported and verified all updates that I copied over from the old server.
But the new server will NOT download anything fresh from Microsoft.
I keep getting error error 364:

Content file download failed. Reason: Value does not fall within the expected range. Source File: /msdownload/update/software/defu/2013/05/am_delta_f1860b39acfcbfcf1d701c7c19d28faa97dd9e71.exe Destination File: D:\WsusContent\71\F1860B39ACFCBFCF1D701C7C19D28FAA97DD9E71.exe.

The proxy obviously supports the Range command properly. After all the other server uses the same proxy and also downloadmanagers have no issue with it either. (Tried another proxy as well: Same issue.)
I have tried setting BITS to foreground mode. Doesn't make any difference.

I have completely removed the WSUS role (including registry keys, etc.) and re-installed. After re-install the problem is back.

There is no other logging that I can find that sheds more light on the problem.

Any ideas what can be causing this ?

Update:

After some experimenting I narrowed it down as follows:
a) BITS jobs are created by the WSUS service, but they get cancelled immediately (same second) after being created. This is visible in the Bits event log messages. (No apparent reason for the cancels.)
b) Server is member of domain X. Account used for proxy is member of domain Y (and has admin rights on the server). On the old machine everything is in domain Y. This may be part of the problem.

I'm going to get an account in X with proxy access and use that for the WSUS transfers. Unfortunately I have some red tape to wade through to get another account so I won't be able to test that today anymore.

Update 2:
After getting an account in the same domain as the server itself I still got the problem. Apparently this doesn't make any difference.
I also tested this new account on th eold working server. (Thus creating the cross-domain issue there.) The other server is happy with it has no issue using the new account.

Tomorrow I'm going to take the deep plunge: Remove the WSUS & IIS server-role completely, remove all related registry keys, remove all content-files from IIS and WSUS and throw away the WID database. Reboot the server and do everything fresh.
I would like to do a full re-install of the OS too but that is not feasible. Servers are managed by another department. I can get full local admin on one, but I am not allowed to install one.

Update 3:
Somehow the Windows installation itself got borked through all the experimenting.
I had to bit the bullet and request a re-install of the server.
…
Ok,
I've got a fresh server-install.
Redid the WSUS setup, by the book.
Same effect: Error 364

I am at my wits end. What can possibly be causing WSUS (or BITS) to think the downloads are problematic ? (BITS just immediately cancels the downloads without actually doing anything.)
I'm guessing the real problem is something else, which isn't handled properly and leads to this misleading error 364.
Any suggestions towards a solution, or just things to try for trouble-shooting are welcome.