You can technically clock each one differently in ATI Catalyst Control center using the "Select GPU to configure" drop-down here:

I know for a fact that clock differences aren't a dealbreaker in Crossfire because my two 5870s have slightly different clocks (850 vs 875) and it works fine.
However, the nature of the work (either rendering fragments of the screen, or alternating frames of the screen) means that synchronized clocks are best. I'm planning to down-clock both cards to the same 850 Mhz.
I personally would be very very hesitant to overclock a Crossfire rig at all, as they are already more complex, generate tons more heat, etc.