Trying to sort this out in steps...
1] Internet Explorer at Startup
I would have to wonder why IE gives a "Not responding" message at startup as that is unusual.
Can you give the full error message? Sometimes Windows will display an error similar to "Explorer not working" and users often confuse this with Internet Explorer, where it is more than likely Explorer as in Windows Explorer, (eg your Desktop itself, or any of your My Documents folders).
If it definitely is Internet Explorer, check your Startup folder in the Start Menu bubble > All programs list. Is there an entry in that folder for internet Explorer, or for a web site? If so that is forcing IE to load at startup and I would remove that entry, (right click, select Delete).
If there is no entry in that Startup folder, you next need to check the "System Configuration Editor". In the Start bubble Search option, type in Run. If a Run entry is found at the top of the list, click that. In the new box that opens, type in msconfig, (For clarity, that is MSCONFIG). In the new window, goto the Startup tab and look down the list either for an IE entry or for a web site entry. If you find one, remove the tick, then click Apply/OK.
Hopefully that will clear the Startup problem.
2] Internet Explorer not responding
Often these problems can be traced back to bad or corrupted Add-ons. You can check IE's Add-ons from within IE by going to Tools > Manage Add-ons, then check through all the add-ons, plugins and ActiveX and try an elimination test.
Alternatively you can goto IE's Tools > Internet Options, then the Advanced tab, and click the "Reset" button. This resets IE back to it's default state and removes all add-ons and third party toolbars and so on, but beware, this may also remove all Favorites, all History and Cookies, and any web site logins and passwords you have saved in IE.
3] Windows Updates
You don't say what the problem is with Windows Updates, so diagnosing is difficult, but since malware can often attempt to prevent users from updating Windows I would try some anti-malware scanning in addition to your normal anti-virus scanning with either or both of the two utilities below;
Malwarebytes' Anti-malware and SUPERAntiSpyware
I hope that helps.
Mark
I frequently get the message "Internet Explorer Not Responding" even when I first switch on. This is so frustrating that I have installed Firefox and Opera as alternatives when the problem is particularly bad. However, overall I do prefer IE as my search engine and would be grateful if someone has a solution to this problem. I also have a problem with Windows Updates which will not install and wonder if there is a connection.
Ipar13

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic