When I use unicode-normalize($string, "NFKD") (or "NFD", or any other normal form), $string is not normalised to the requested normal form (without any error message); a decomposed string is left untouched, though. I tried with Java 1.6.0_20-b02-279 on a Mac (OS X 10.6.3) and ICU 3.8, 4.0, 4.2, 4.4.
To reproduce, try:
(: composed, unless SF normalises :)
(: decomposed, unless SF normalizes :)
I was finally able to normalise using the java bindings and java.text.Normalizer via a tiny caller class (using java bindings, java.text.Normalizer.Form does not seem to be accessible).