Okay - This has been a problem with IE for as long as I can remember
Let's try this: a) Open IE; b) Maximize the IE window - If you use Autohide for the Taskbar, turn Autohide off before maximizing the window; c) After maximizing the window, increase the height of your taskbar from one row to two (left click and hold the top edge of the taskbar and drag it up. Wait for the IE window to re-size; d) Then drag the Taskbar back to its normal size - the IE window will re-size again; e) Close IE and re-open it - it should open maximized. If it doesn't, reboot the computer.
EDIT: In step c), make sure to "unlock" the Taskbar before trying to re-size it.