What is our immediate purpose? To test the RAM itself or the installation? Are all the address lines tested with a 0x00,0x55,0xaa,0xff pattern like the data lines are, or do only the high address lines get hit as sparse locations are tested?

I'd argue that the nature of the upgrade merits hitting all of the address lines, but that a full memory test is not necessary for the Mk2/Mk2a (assuming that the chips were handled properly.)

The Mk1 is an interesting case. We know from Hugo that the Mk1 chips have a known high failure rate, and we also know that the upgrade itself is easier and less prone to problems.

Anyway, http://www.esacademy.com/faq/docs/memtest/index.htm has useful strategies for testing data lines, address lines and a full device test. They even have sample code that could be adapeted.