Found a solution for my annoying toolbar changing behavior between IE and Explorer.

Go to:

HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\Toolbar\ShellBrowser

and Set the Permissions for your account to Deny. Haha, take that Windows. Try and change things now.