I agree fully with all the comments previously reported on the challenging topic you raised.

You might want to have a look at the following:

- Rand index (implemented in "R" http://www.r-project.org/ , in the package e1071 subroutine classAgreement)
J.~Cohen. A coefficient of agreement for nominal scales. Educational and Psychological Measurement, 20,37-46, 1960. Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of Classification, 2, 193-218, 1985.

- Linear measure of cluster quality        
Mather L.A.  JOURNAL OF THE AMERICAN SOCIETY FOR INFORMATION SCIENCE. 51(7):602-613,2000
- amendment of the above paper        
Toldo L, JOURNAL OF THE AMERICAN SOCIETY FOR INFORMATION SCIENCE AND TECHNOLOGY,52(7):602, 2001
-Java implementation of the linear measure of cluster quality
Toldo L, Cluster Validity Abstract # 83 Third International Meeting on Microarray Data Standards, Annotations, Ontologies and Databases March 29-31, 2001, Stanford University

simply email me if you want a copy of the Java implementation of the LAMCQ algorithm.

Regards
Dr. Toldo