Sounds like the update that was downloaded is not installing after it has been downloaded. I have never had auto update turned on, I may not know what exactly each update is but I still like to see them before I install them.
I hated the popup balloon advising me auto updates was turned off each time I booted, (I'm running XP Pro SP3 with all updates) did a little searching and found how to stop it. Go to control panel>security center and turn Automatic Updates off, in that same box on the left side under resources click on "Change the way Security Center alerts me". In the box that comes up uncheck the "Automatic Updates" box. This stopped any alerts on my machine. You might reboot after changing those settings to see if anything changes on a shutdown. I don't know if you will see any difference the first time. Might fix it up on subsequent shutdowns.
Then I would go to Microsoft Updates and check for critical updates, allow it to download anything it finds, then see what gets installed. There might be something on the microsoft website about a particular KB update if it won't install on your machine, I've put a link to their help and support page below. Microsoft Support