I upgraded to Java 7 and Redcar 0.13 and have re-looked at this issue. Here is what I found: Java 7 seems not to rely on JAVA_HOME\bin being on your path but rather copies java.exe, javaw.exe, javaws.exe to \Windows\System32 which is of course on the path anyway. I'm not sure whether that's different from what Java 6 does, in any case, it's what Java 7 does. Redcar does not work by default with this configuration.
In this thread people talk about JAVA_HOME being on your path, but it's important to distinguish between JAVA_HOME, which is something like C:\Program Files\Java\jre7 (or the JDK equivalent) and the directory which has the Java executables, which is JAVA_HOME\bin, i.e. C:\Program Files\Java\jre7\bin in this example.
Adding JAVA_HOME to your PATH will not change anything. However if you add JAVA_HOME\bin to your path, redcar will work. I've no idea why Redcar is happy with the binaries in the JAVA_HOME\bin folder and not those in the System32 folder. But that's how it is.
John