With the unit.
Yes the event viewer will show you the shutdown & restart times.
Windows Patches are not listed by Name or anything else except date so if there is something there you would have to open the Windows Live Update Web Page and check for previously installed Updates by looking at the install History. Which will also tell you when the last set of updates where installed and what they where, But not all are removable.
As for your last questions without knowing why you are doing this I can not answer them with any certainly but my [b]Gut Feeling[/b] is a most defiant [b]NO![/b] If you want to remove any installed Patches use the Add Remove Programs option in the Control Panel but absolutely nothing else unless of course you really want to perform a new install from scratch.
Much More Importantly why do you have the Auto Updates turned on and allow them to install without supervision? This is a really dangerous thing to do as you loose control of the server so you my as well forget about any form of security as you are unaware of what is happening to the unit and trusting M$ to do the right thing is like playing [b]Russian Roulette with a Fully Loaded Pistol.[/b]
Col