Basically, I compute a CRC32 on the data ... I tried MD5 originally but WOW was it slow.

You might want to try Adler32. It should be faster than the CRC and it's built into Java (at least 1.3 and 1.4).