The subject behavior will occur if you try to remove Internet Explorer 6 from a Terminal Server-based computer, and the Terminal Server is NOT in Install mode.
To resolve this problem:
01. Open a CMD prompt.
02. Type Change User /Install and press Enter.
03. When you receive User session is ready to install applications, type exit and press Enter.
04. In Control Panel, double-click Add/Remove Programs.
05. Depress the large Change or Remove Programs in the upper-left corner of the Add/Remove Programs dialog.
06. Select Microsoft Internet Explorer 6 in the Currently installed programs list and press Change/Remove.
07. Select and follow the Restore the previous Windows Configuration option.
08. After the restart, open a CMD prompt.
09. Type Change User /Execute and press Enter.
10. When you receive User session is ready to execute applications, type exit and press Enter.