Actually, you mention a Startup repair, but did you look at the link? I suggested a Repair install. It will save your programs and settings, but repair the windows installation. I am very surprised you were able to remove IE completely. Windows itself uses IE. Can you still run Windows Update? Does it work correctly? That uses IE. You might try system restore from a command prompt in safe mode:
Boot to Safe mode with command prompt
> When command prompt loads type rstrui.exe
See if you can then access System Restore.