E.U.A,
Like Bill said - maybe answer is in display's speed and processor and LCD timing?
2) compiled for 16MHz but run on 20MHz - "slower" version is run faster and when processor is checking if LCD is ready - it's not ready and processor need to wait. More often it check and miss - more clocks it lose.
3) faster version run on slower clock - better hit ratio 
Do you have another LCD?
robin