When you try to remove Java, do you see an error something like 'fatal error during installation'?

Check out post #11 in the thread below. The first link in post #11 has info about a MS cleanup utility - see whether that helps at all
LimeWire Problem with Java Runtime Enviroment Please Help