This may have long since been solved, but I too have had this problem. I think it occurs when I manually run Windows Update, rather that have it do its stuff automatically, but whatever.
I finally found that a program, "ExplorerXP," which mimics the behaviour of the Windows Explorer which came with Windows XP (my current OS is, sigh, Vista) will let me delete the many empty directories which Windows Updates saves on my C: drive.
I start it with a right-click and run as Administrator, and it is a bit slow to start, but then I can mark a range of MSI*.tmp directories and delete them in one go.
I am not sure if this is a prerequisite, but when I was struggling to get rid of the files before discovering the above, I made sure that I had permission to delete all files in the root directory of my c: drive (for some reason this was not the case).