XSD:XML Is there a better way to check for unique?

I am using xsd:key to make sure that values are unique. However, that validation restriction drastically slows down the processing. I've tried removing the keys and then using xpath query statements after the normal validation, but it seems to take about the same amount of time.

My tests are:
3000 records = 6 sec without keys
3000 records = 40 sec with keys

5000 records = 11 sec without keys
5000 records = 138 sec with keys

The 10k recordsets take an incredibly long time to check with keys.

Are there any optimzation techniques that I can use to help discover duplicate values in a time efficent way? Or will the key elements of the XSD result in about the same time as doing the xpath query after normal validation?

thanks,