Despite multiple articles of howto maintain a WSUS database for performance and scalability – there was always a performance issue dragging across which made all the cleanup jobs take forever. An earlier (not able to find it again) Technet Forum post clarified that this was due to all clean-up jobs beeing dependent on the Stored Procedure spDeleteUpdate, and this generates a temporary table that doesnt have an index for the appropiate columns. Unfortunately I werent able to find this post again – but lo, and behold – Microsoft confirmed the behaviour!
The fix is simply to alter the Stored Procedure spDeleteUpdate and append the following line during the creation of the temporary table;