Open IE, just have one IE window open. If it is maximized restore the window. Resize the window manually to be full screen, then close it.
IE opens windows in a restored state based on what the main window's restored size. This is the only way I know how to fix this (new windows that open up sized differently won't mess this up as long as the last window closed has the "maximized" normal state, also windows that can't be resized won't hurt it either).