Procedure:
1. Check that machine is clean of all previous Java JDK installs.
 i.e.
no traces in Add/Remove
no C:/j2sdk1.4.2_12 directory
no key [HKEY_LOCAL_MACHINE\SOFTWARE\JavaSoft] in registry.

2. Install 1.4.2_12b01 jdk bundle

**NOTE: Exclude Demos, Source Code and Public Java runtime to save time
and distinguish reponsible agent of the problem.

Verify that installation provides the following system components:

Folder C:/j2sdk1.4.2_12

Registry keys:
Windows Registry Editor Version 5.00

[HKEY_LOCAL_MACHINE\SOFTWARE\JavaSoft]

[HKEY_LOCAL_MACHINE\SOFTWARE\JavaSoft\Java Development Kit]
"CurrentVersion"="1.4"

[HKEY_LOCAL_MACHINE\SOFTWARE\JavaSoft\Java Development Kit\1.4]
"JavaHome"="C:\\j2sdk1.4.2_12"
"MicroVersion"="2"

[HKEY_LOCAL_MACHINE\SOFTWARE\JavaSoft\Java Development Kit\1.4.2_12]
"JavaHome"="C:\\j2sdk1.4.2_12"
"MicroVersion"="2"

3. Remove the 1.4.2_12 JDK and reboot.
Observe the following artifacts remain:

Folder(empty) C:/j2sdk1.4.2_12
Registry key(value not set): [HKEY_LOCAL_MACHINE\SOFTWARE\JavaSoft]

All keys and folders should be removed following JDK removal.

NOTE: This is _not_ a regression from 1.4.2 FCS.
Same behaviour observed there.
Note that the problem was observed on Windows XP Home SP2 x86
I was able to reproduce this on Win XP Pro SP2 machine with j2sdk1.4.2_12 b3.
I observe that when j2sdk1.4.2_12 is removed, the c:/j2sdk1.4.2_12 dir. and JavaSoft registry key in question still remain, although are empty.
Expected behaviour is like submitter said, the c:/j2sdk1.4.2_12 should be removed itself and also the JavaSoft key in the registry also.

I can make the machine available for vnc testing for your convenience.