For those reading this thread, Richard sent us the t80 archive (thanks Richard), so we could investigate this. The short answer is that the core didn't have a timing constraint set, so recent versions of Quartus (4.1 and later) just work to achieve routability, and do not fully optimize its timing. Setting an aggressive clock period constraint dramatically speeds up the core when run through Quartus.
I compiled the t80a core in Quartus II 5.0 SP1, and achieved 42.74 MHz, which matches Richard's result. However, I noticed that there are no timing requirements set -- in that case Quartus will try to compile the design as fast as possible, and will not fully optimize the design for timing.
I went to Assignments->Timing Settings and set "Default required Fmax" to 100 MHz. Then I recompiled.
With that assignment, Quartus achieves a frequency of 75.53 MHz for this design.
It is a general rule that you should set an aggressive (unachievable) timing assignment when you want to see how fast a design can go. Alternatively, you can choose Settings->Fitter Settings->Standard Fit, which essentially makes the most common type of unachievable timing requirement (Fmax on all clocks) automatically for you.
To get even more speed, you can also turn on physical synthesis (all options) under Assignments->Settings->Physical Synthesis Optimizations. On this design, turning physical synthesis on (+ having a 100 MHz default Fmax) yields a speed of 83.43 MHz.
Vaughn Betz A;tera [v b e t z (at) altera.com]