Recently, I could generate successfully a 640x480 @70Hz via Mega 2560
That sounds ... impossible. 640x480x70 is a minimum dot clock of over 21MHz, and you can't get that from a 16MHz AVR.
I do not focus on pixel information, but on the stable V and H sync.
So it's got 640x480 VGA HS/VS timing, but supports some random number of actual pixels on each line? That seems more likely...
The thing is, that code is very tight to current processor speed, full of NOPs and adjustments
That is how such code is usually written; interrupts or even timers have WAY too much overhead.