Clock recovery violated: what to do?

At first glance, recovery is solved just like a setup violation, by reducing the levels of logic between registers, moving them closer together, etc. That being said:

1) Is there any logic between the registers? Usually recovery is a register to register path, which usually makes it easy to meet timing(you generally don't want combinatorial logic on recovery paths since it feeds an asynch port on the destination register and a glitch would cause it to swtich).

2) What's the requirement between the two registers? It's crossing domains, so maybe the requirement is unrealistic.

3) Are you sure this is a valid path, i.e. that it has to make timing? This is something you probably can't say since it's not your code(I don't see the whole path, so not sure), and have to assume it does need to meet timing.