Compilation time for Quartus II 9.0

Yowsers. At the end of the day, I think it is what it is. Routing is probably the biggest use of silicon in an FPGA, so they're really not designed to have lots of extra resources to fix hold violations. You may try to manually add delay to your clock trees and see if theres any way to balance them. (I don't know how many clocks you have, if they're on globals, etc.) One other thing of note is that in Q9.0 they added an "Estimated Delay Added for Hold" table, or something like that. You're already aware of why it's being added, but might be a good chart to gauge what the router is doing.